Context-free grammar for $L = \{ a^n b(b^* \cup aa^*b)a^n: n \in \mathbb{N}\}$

Question

How can I change the language $$L = \{ a^n b(b^* \cup aa^*b)a^n: n \in \mathbb{N}\}$$ to a context-free grammar? To create The symmetry of with the $a^n$, then it is clear I have to use $S \rightarrow aSa$ and $S \rightarrow \epsilon$, but it is very unclear to me how to generate the grammar of $(b^* \cup aa^*b)$.

Answer 1

Finite union can be obtained by designating a symbol to go to one of finitely many other symbols, each of which generates one set from the union.

So $S\rightarrow A$, $S\rightarrow B$, $A\rightarrow bA$, $A\rightarrow \epsilon$, $B\rightarrow aCb$, $C\rightarrow aC$, $C\rightarrow \epsilon$ should work so that $S$ generates $(b^*\cup aa^*b)$ (we have that $C$ generates $a^*$, $B$ generates $aa^*b$ and $A$ generates $b^*$).

You will not want $S\rightarrow \epsilon$ as a rule, as then $S$ just generates $(aa)^*$. Instead, have a rule where $S$ goes to a variable that generates $b(b^*\cup aa^*b)$.

Is it clear how to combine these two pieces of information together to solve the problem?

Answer 2

So you know how to generate the same number of a as prefix and sufix. What you need to know is how to generate the string at the center. In place of using $S \rightarrow \epsilon$, S should produce another variable, let's say C. Then C must produce the center string and for that, you just need to know how to convert a Regular Expression in a Grammar. There are three operations in R.E.: union, concatenation and Kleene Star.

1. Union: (a|b) can be represented as a grammar with two productions: $X \rightarrow a$ and $X \rightarrow b$
2. Concatenation: (ab) can be represented by $X \rightarrow ab$
3. Kleene Star: (a*) can be represented by $X \rightarrow aX$ and $X \rightarrow \epsilon$

To transform $b(b^* \cup aa^*b)$, the first thing you need to think is how priorities are solved in a R.E. First priority is Kleene Star, second is concatenation and last is union (parenthesis change priorities, of course). So, you have to convert first $b^*$. Applying the rule 3, you get $Y \rightarrow bY$ and $Y \rightarrow \epsilon$ (you are going to create one new variable for each operation). If you follow these instructions you should reach a correct grammar for your R.E.

If you need more explanation, please ask.