I would like to prove the context-free language $$ \mathcal{A} = \{ w\#x ~:~ w^R \text{ is a substring of $x$ for } w,x \in \{0,1\}^* \}, $$

has the context free grammar

\begin{align*} S &\rightarrow TX\\ T &\rightarrow 0T0 ~|~ 1T1 ~|~ \#X\\ X &\rightarrow 0X ~|~ 1X ~|~ \epsilon. \end{align*}

However, it is not clear to me how this is even true. First I examine $X$ and note $X$ generates a string with arbitrary mix of $0$'s and $1$'s. Furthermore the string could begin or end with $0$ or $1$. But I do not see how $T$ could generate a string whose reverse is a substring of $X$. In particular, $T$ is defined in terms of $X$, so isn't $T$ always longer than $X$?

As a simple example, let $X = 0$, and $T = \#X = \#0$, then $S = \#00$, and this string is not in $\mathcal{A}$!


You’re correct in thinkint that the proposed grammar doesn’t work. What you want to do is generate $w$ and $w^R$ first, much as you’ve tried to do with $T$, and then take care of the rest of $x$ and the $\#$. Assuming that you don’t want $S$ to appear on the righthand side of any production, you might begin with this:

$$\begin{align*} &S\to 0T0\mid 1T1\mid X\\ &T\to 0T0\mid 1T1\mid X \end{align*}\tag{1}$$

When you finally generate $X$, you’ll have $wXw^R$ for some $w\in\{0,1\}^*$. Clearly the $X$ can be used to generate $\#u$ for any $u\in\{0,1\}^*$, so we can extend $(1)$ with some $X$ productions to generate anything of the form $w\#uw^R$, but this isn’t quite good enough: it forces the $w^R$ to be at the righthand end of $x$.

If $w$ is the empty word, this isn’t a problem, so the production $S\to X$ is fine, but if $w$ is not the empty word, we must be sure to allow for something to the right of $w^R$. We can do this by modifying the first line of $(1)$ slightly:

$$\begin{align*} &S\to 0T0Y\mid 1T1Y\mid X\\ &T\to 0T0\mid 1T1\mid X \end{align*}\tag{2}$$

The grammar fragment in $(2)$ will give us $X$ and anything of the form $wXw^RY$, and you shouldn’t have too much trouble figuring out what $X$ and $Y$ productions you need to add to $(2)$ to get a grammar that generates $\mathcal{A}$. Once you’ve done that, we can worry about actually proving that your grammar works as intended.


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.