2

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

Herious
  • 157

2 Answers2

3

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

Brian M. Scott
  • 616,228
  • you mean like A -> aa|ab|ba|bb|epsilon ? – Herious Aug 25 '13 at 00:17
  • @Herious You don't want the epsilon, as you don't want $A$ to be empty. – Evan Aug 25 '13 at 00:19
  • oh I see, thanks so much, may I ask how did you come up with the solution? These problems seem to not have any rule to solve... – Herious Aug 25 '13 at 00:25
  • @Herious: The idea of a non-terminal that spits out matched pairs on opposite sides is pretty standard. Once you have that, it's not hard to see that you can build anything between the resulting strings $v$ and $v^R$ that doesn't depend on whatever is outside them. Similarly,it's not hard to see that you can also build anything before or after them that can be generated by a non-terminal. – Brian M. Scott Aug 25 '13 at 00:53
0

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.

Peter Halburt
  • 365