World's most popular travel blog for travel bloggers.

[Solved]: Context free language and the complement of it

, , No Comments
Problem Detail: 

Given the language $L_1 = \{a^i b^j c^k \mid i \neq j \vee i \neq k\}$, I need to determine whether it is context-free by using the pumping lemma. I must do the same for the complement of this language.

I started off by breaking $L_1$ into two parts, $L_1 = L_2 \cup L_3$, where $L_2 = \{a^i b^j c^k \mid i \neq j\}$ and $L_3 = \{a^i b^j c^k \mid i \neq k\}$, and I proved that both the languages are not context free, hence the union which is $L_1$ is also not context-free. Is this approach of mine correct?

Also would the complement of $L_1$ be $L_1' = \{a^i b^j c^k \mid i = j \wedge i = k\}$ and break down $L_1'$ into two parts $L_2'$ and $L_3'$ and by the closed under intersection rule for context-free languages we know $L_1' = L_2' \cap L_3'$ is not context free.

This how I approached both the parts, and I would like to know if my approach is correct or wrong. Help would be really appreciated.

Asked By : SSH

Answered By : Hendrik Jan

Sorry, your approach does not work.

Breaking down $L_1$ into two parts is a good idea. Unfortunately you proof these parts are context-free cannot be correct, as one can give a grammar for each of them.

As for the complement, there is no such thing as a intersection rule. The fact that context-free languages are not closed under intersection simply states that there exist two context-free languages the intersection of which is not context-free. The intersection of any random pair of context-free languages can be context-free (e.g., if the intersection is empty).

Back to the drawing board.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback