Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

So far, this is the solution that I have been able to come up with, though I am not sure how accurate it is:

$$\begin{align*} S &\to aSa \mid X \\ X &\to bX \mid a \mid \varepsilon \end{align*}$$

I worked this out from outside first, which gives me the first and last a's and then used the second rule to get the b's or a's after.

The reason I came up with that answer, I thought the grammer need to start and end with "a" and then have b's in between those a's.

So for each letter with different power we need to have a rule? That is, for $a^i$ we need a rule and for the $n$ power we need another one ?

  • $\begingroup$ If you are given a PDA that accepts the language, there is a recipe to convert that PDA to a CFG, which is not easy to follow by hand usually, though. $\endgroup$
    – John L.
    Dec 17 '18 at 15:08

You could break down the language into simpler parts, e.g., you can generate languages separately for $a^i$ and $b^na^n$, then concatenate them in the end (we know that CFG's are closed under concatenation).

In your case, you can do

A $\rightarrow$ aA | $\epsilon$

to generate $a^i$, and

B $\rightarrow$ bBa | $\epsilon$

to generate $b^na^n$, then concatenate by doing:

S $\rightarrow$ AB


You have created a grammar for $\{ a^i b^k a^j \mid i, k \in \mathbb{N}_0, j \in \{ i, i + 1 \} \}$, which is not what you wanted.

Hint: Try to generate the a's and b's for the $b^n a^n$ part simultaneously.


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.