0
$\begingroup$

$\{a^nb^2a^n \mid n \ge0\}$

I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between.

I came up with the following grammar, but I think it accepts strings that it should not such as: $abb, bba$, etc.

$$\begin{align} S&\rightarrow X\\ X&\rightarrow XbbX \mid \epsilon\\ A&\rightarrow aA \mid \epsilon \end{align}$$

$\endgroup$
  • $\begingroup$ Your grammar doesn't generate any word with an $a$ in it. $\endgroup$ – David Richerby May 11 '14 at 7:37
3
$\begingroup$

In dealing with CFGs, it's often useful to work from the inside out. Clearly $$ S\rightarrow aSa $$ will generate all strings of the form $a^nSa^n$, for $n\ge 0$. Then all you have to do is allow the possibility that $S$ will also eventually generate $bb$, which we can do by the production $S\rightarrow bb$, giving the grammar $$ S\rightarrow aSa\mid bb $$ or, if you wanted to be explicit about the $bb$ central part, you could write $$\begin{align} S&\rightarrow aSa \mid T\\ T&\rightarrow bb \end{align}$$ The problem with your grammar is that it can't guarantee that there will be the same number of $a$s on each end of a generated string.

$\endgroup$

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.