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 : http://cs.stackexchange.com/questions/18337 3.2K people like this
