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
    @Yuval, $d$o 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.