CODEWITHSUNDEEP
subsetcontext-free-grammarcontext-free-language
AIM
AIM

Reputation: 137

Trying to prove that the complement of {a^i b^i c^i} is a context-free

I'm trying to prove that the complement of L= {a^i b^i c^i : i >= 1} is a context free. L complement is: {w is a word over {a,b,c}* : w not in L}.

As we know, context-free languages are closed under union. So, I'm trying to divide my language (complement of {a^i b^i c^i}) into context-free subsets in which their union must be context-free. Could anyone help me to find the subsets? Each time I try to, I end up with L*!

Thank you.

Upvotes: 0

Views: 2192

Answers (1)

rici
rici

Reputation: 241911

Note: In the following, I left out the constraint that L does not include the empty string, but that only requires a small adjustment.

Consider aibjck.

If i=j and j=k then you have aibici. Conversely, if i≠j or j≠k, then you have the part of the complement of aibici which consists of strings in a*b*c* (the rest of the complement is straight-forward).

In other words, 

L = { aibjck | i=j } ∩ { aibjck | j=k }
and 
L' = { aibjck | i≠j } ∪ { aibjck | j≠k }
 It's easy to show that each subset in the above equations is context-free. As you say, context-free languages are closed under union, but they are not closed under intersection; consequently, L' is context-free even though L is not.

Upvotes: 5

Related Questions