Consider the following language: $$L_4 = \{a^ib^jc^kd^l : i,j,k,l \ge0 \wedge i=1 \Rightarrow j=k=l\}.$$ Prove or disprove: $L_4$ is a context-free language.

To me, it looks like $L_4$ can be accepted using a PDA, but I don't know how to construct it. appreciate a hint here.

  • 3
    $\begingroup$ The sub-language for $i=1$ is not context.free $\endgroup$ – Wuestenfux Dec 22 '18 at 13:42
  • $\begingroup$ Can you give me a hint of how to disprove it then? $\endgroup$ – Yotam Raz Dec 22 '18 at 14:48
  • 1
    $\begingroup$ The pumping lemma for context-free languages would do it. $\endgroup$ – Henning Makholm Dec 22 '18 at 14:54
  • $\begingroup$ is $w = ab^kc^kd^k$ a good choice? for $k$ being the constant from the pumping lemma. $\endgroup$ – Yotam Raz Dec 22 '18 at 15:03
  • 1
    $\begingroup$ More precisely, what the pumping lemma shows directly is @Wuestenfux's claim. To get all the way to $L_4$, note that "the sub-language for $i=1$" is the intersection of $L_4$ and a regular language. $\endgroup$ – Henning Makholm Dec 22 '18 at 15:50

Since the context-free languages are closed under intersection with a regular language and under homomorphism, if $L_4$ were context-free then so would the following language be, for the homomorphism given by $h(a) = \epsilon$ and $h(\sigma) = \sigma$ for $\sigma \neq a$: $$ h(L_4 \cap a(b+c+d)^*) = \{ b^nc^nd^n : n \geq 0 \}. $$ However, the latter language is well-known not to be context-free.


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.