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 : http://cs.stackexchange.com/questions/18337
0 comments:
Post a Comment
Let us know your responses and feedback