Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
@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
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|cite|improve this answer

Your Answer


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