Is $L_4$ a CFL?

58 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST 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.