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.

  • $\begingroup$ 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. $\endgroup$ – Musicode Mar 20 '14 at 3:51
  • $\begingroup$ @Musicode: I would, but I don't understand my own thought process. Sorry. $\endgroup$ – user2357112 supports Monica Mar 20 '14 at 3:58

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.