# Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

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 ?

• 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. – 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.