Consider the following statements

  1. $L_1 = \{wxw^R \mid w∈(a,b)^*, x∈c\}$
  2. $L_2 = \{wy \mid w,y∈(a,b)^*\}$
  3. $L_3 = \{zwz \mid w∈(a,b)^*,z∈\{a\}\}$
  4. $L_4 = \{wxw \mid w∈(a,b)^*,x∈\{c\}^*\}$

Find the classes of languages?

My attempt:

Obviously $L_1$ is deterministic context free language.

$L_2$ is regular language as regular expression is $(a,b)^*(a,b)^*$.

$L_3$ is also regular language as regular expression is $a(a,b)^*a$.

I'm stuck at $L_4$ it seems context sensitive language but not context free language

Can you explain in formal way, please?


The language $L_4$ is not context-free. Indeed, if it was, then $L_4 \cap \{a,b\}^* = \{ ww \mid w \in \{a,b\}^* \}$ would also be context-free. But it is not: see for instance this answer by Brian M. Scott.


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.