2
$\begingroup$

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.

  • 1
    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.2011-02-27
  • 1
    @Yuval, do make that a proper answer, so that this does not end up being periodically revived by the annoying *Community* user.2011-02-27

1 Answers 1

3

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