0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.