1
$\begingroup$

I am trying to develop a CFG for the language $L$ defined by:

$L = \{a^{n+2}bba^{n-2} | n > 1\}$

The problem I am having is that I cannot develop the CFG for this language no matter what I try. The closest I can get is:

$S \rightarrow aaaaXbbX$ (Production 1)

$X \rightarrow aX | \Lambda $ (Production 2)

This would be right if we were somehow forced to substitute the same value of the non-terminal $X$ in both its appearances in production 1. However, we can substitute $X \rightarrow aX$ in its first apperance in production 1 and $X \rightarrow \Lambda$ in its second appearance in production 1, thus throwing the balance of $a's$ off as defined in the language $L$.

The first question is, is there even a CFG for this?

Well, I would say according to theory, yes there is because:

  • I am asked to draw a Determinate Push Down Automata for this language; and
  • According to theory, every language accepted by a PDA is context-free

Am I correct that there is a CFG to this and what is it?

$\endgroup$
  • 1
    $\begingroup$ Welcome to ComputerScience@SE. Can you please edit into your question how to interpret whilst knowing the number of terminals from the title? I see an unknown $^n$. $\endgroup$ – greybeard Feb 2 at 7:20
4
$\begingroup$

Your attempt was pretty close! But I think that this is the way to go for you

$$S \rightarrow a a a a X$$

$$X \rightarrow a X a \mid b b$$

The way that these rules come together forces there to be the four necessary $a$'s at the start and then it's a matter of matching $a$'s with $b b$ in the middle.

So after that, it's a question of making a CFG that generates $L = \{a^n b b a^n \mid n \geq 0\}$. That's exactly what $X$ does. Every time you see a $X$ you have to put a leading and trailing $a$ in and you can't terminate until you put the $b b$ in the middle since otherwise the $X$ gets expanded to another $X$.

$\endgroup$
  • 1
    $\begingroup$ I am impressed at how you picked up this answer. Is it purely a matter of practice or is there a quasi-algorithm that can help guide me in determining future CFG's? $\endgroup$ – Dean P Feb 1 at 17:45
  • 2
    $\begingroup$ I'd say its mostly practice. There might somewhere be an algorithm for dealing with CFGs like you can regular expressions with Kleene algebra but I've never seen it before if it exists at all. $\endgroup$ – Matt Werenski Feb 1 at 17:51
  • $\begingroup$ @MattWerenski such a beast is quite unlikely, as it is undecidable even if two grammars generate the same language. $\endgroup$ – vonbrand Feb 19 at 1:10

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.