The language

$$L = \{x^r \# y | x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$

where $x ^ r$ denotes the backward written word x, is context-free.

Can someone explain, if this statement is true? I am not able to construct a PDA, so I think the language is not context-free. Does anyone have an idea how to prove it?


A more precise expression of the condition "$x$ is a contiguous substring of $y$" produces

$$L = \{x^r \# wxz | x, w, z\in \{a, b, c\}^*\}$$

That should make it clear that the language is context-free.

  • $\begingroup$ Thank you for your answer! Do you have an idea how to prove that it is context-free? I am not sure how to include "w" and "z" in an context free grammar. $\endgroup$ – user101036 Feb 28 at 0:00
  • $\begingroup$ @x_x: since they are both unconstrained, they are just $\Sigma^*$, which should not be hard to write a grammar for. $\endgroup$ – rici Feb 28 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy