[Math] Find context free grammar for $u v w v^R$

context-free-grammar

The question is to find a CFG for this language:

$$\{ u v w v^R\ |\ u, v, w \in \{a,b\}^+,\ |u| = |w| = 2\},$$

where $v^R$ denotes the reverse of $v$.

I've been trying, but I'm not sure how to have $w$ in between $v$ and $v^R$.

Just for the v and v^R, I can do S -> aSa | bSb | epsilon

Best Answer

Have a non-terminal symbol $A$ that generates any string of two terminal symbols and disappears. If $S$ is the initial symbol, have a production $S\to AB$, where $B\to aBa\mid bBb\mid aAa\mid bAb$.

Related Question