# Is $L_4$ a CFL?

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.

• The sub-language for $i=1$ is not context.free – Wuestenfux Dec 22 '18 at 13:42
• Can you give me a hint of how to disprove it then? – Yotam Raz Dec 22 '18 at 14:48
• The pumping lemma for context-free languages would do it. – Henning Makholm Dec 22 '18 at 14:54
• is $w = ab^kc^kd^k$ a good choice? for $k$ being the constant from the pumping lemma. – Yotam Raz Dec 22 '18 at 15:03
• 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. – Henning Makholm Dec 22 '18 at 15:50

## 1 Answer

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.