Find context free grammar for $u v w v^R$

1.6k Views Asked by At

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

2

There are 2 best solutions below

4
On 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$.

0
On

A simple application of the pumping lemma shows that this is $\mathbb{NOT \space A \space REGULAR \space LANGUAGE}$ and so you $\mathbb{CANOT}$ use a regular expression. You need to define a CFG.