1
$\begingroup$

Was analysing old exam, still, even in home condition can answer this:

Determine which of the following languages over the alphabet $\{a,b,c\}$ are context-free. Prove the claim.

(a) $L_1 = \{a^nb^mc^k \mid n \leq m \leq k\}$,

(b) $L_2 = \{a,b,c\}^* \setminus L_1$, that is, $L_2$ is the complement of $L_1$ from (a).

Any help would be appreciated, it doesn't seem like CFL to me, but I struggle to apply pumping lemma here.

$\endgroup$
1
$\begingroup$

The language $L_1$ is not context-free, and you can show this using the pumping lemma. Try to pump the word $a^nb^nc^n$ where $n$ is large enough.

The language $L_2$, in turn, is context-free. This is because we can write it as a union of context-free languages:

  • Words not of the form $a^*b^*c^*$.
  • Words of the form $a^nb^mc^k$ where $n>m$.
  • Words of the form $a^nb^mc^k$ where $m>k$.
$\endgroup$
  • $\begingroup$ Thanks. Got answer 8 in morning, at 9 had redo of exam... Surprise, surprise - this question was there too. 1) part would possibly figure out myself, was very close independently. But for 2) - warmest thanks. Wouldn't think myself. $\endgroup$ – Timo Junolainen Jan 9 '17 at 13:33

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.