# Develop the context free grammar to match this language (puzzle)

This is a puzzle type question which asks to create a context-free grammar to match this language:

{ x#w | x,w are in {a,b}*, and w contains the reversal of x as a substring }


So some example strings to try: #, a#a, b#b, ab#ba, ab#aaabbba

Does anyone have any advice on how to get better at these types of problems? I am generally a good problem solver, but have trouble developing grammars for languages for some reason. I am completely stuck on this question. Here is my attempt:

S --> TR
T --> aTa | bTb | #R
R --> RR | 0 | 1 | empty


My guess is that we want to define the left side of the string in terms of the right side of the string.

Edit: As far as I can tell, the above answer seems to be correct now. Only took me an hour to figure out!

Consider the following grammar: $$T \to aTa | bTb$$ It is not hard to check that $T \to^* wTw^R$ for all $w \in \{a,b\}^*$, where $w^R$ is the reverse of $w$.

The language we are aiming at is $\{w\#xw^Ry : w,x,y \in \{a,b\}^*\}$. We can take care of the $x$ part by providing a "leaf case" for $T$: \begin{align*} &T \to \#R \\ &R \to aR|bR|\epsilon \end{align*} Similarly, to take care of the $y$ part, we can create a new start symbol $S$, and add the production $$S \to TR$$ In total, we obtain the grammar \begin{align*} &S \to TR \\ &T \to aTa|bTb|\#R \\ &R \to aR|bR|\epsilon \end{align*}

X --> Xa | Xb | Y

Y --> aYa | bYb | #Z

Z --> Za | Zb | empty


Y is the part that handles the string reversal. X and Z handle junk to the right and left of the reversal of x.

• Mind explaining verbally how you approached solving this, thinking up the answer etc? I eventually figured this out, but it took me way too long. If I had to do this in a short time, I would be screwed. I need a more systematic way to approach these. Mar 20 '14 at 3:51
• @Musicode: I would, but I don't understand my own thought process. Sorry. Mar 20 '14 at 3:58