Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is following language context-free? Alphabet: {a,b,c,d} L = {w | w is not in {aabbc,abc,add}}

I think it is:

{aabbc},{abc},{add} are all regular.

Because of closure properties(Union) R = {w | w is in {aabbc,abc,add}} is also regular. Because of closure of complement (L is complement of R) L is also regular.

So L is regular, and since all regular languages are context-free : L is context-free.

share|improve this question
    
You're right. In fact, any language which is finite or cofinite (a finite number of words is not in it) is regular, and so context-free. –  Yuval Filmus Feb 27 '11 at 20:49
1  
@Yuval, do make that a proper answer, so that this does not end up being periodically revived by the annoying Community user. –  Mariano Suárez-Alvarez Feb 27 '11 at 22:14

1 Answer 1

up vote 3 down vote accepted

You're right. In fact, every finite language is regular, and so is it's complement. They're context-free a fortiori.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.