I have the following language:
$$L := \{b(ab)^n a^m \mid n, m \geq 0\}$$
and have created a right-linear grammar:
Grammar $G(b(ab)^n a^m)$
Terminals $a, b$
Non-terminals $S, S_1, S_2$
Start symbol $S$
Productions
\begin{align*}
S &\rightarrow b \\
S &\rightarrow bS_1 \\
S &\rightarrow bS_2 \\
S_1 &\rightarrow abS_1 \\
S_1 &\rightarrow abS_2 \\
S_1 &\rightarrow ab \\
S_2 &\rightarrow aS_2 \\
S_2 &\rightarrow a
\end{align*}
I'm finding it hard trying to convert the above grammar into a left-linear grammar. Would appreciate if someone is able to help me. I've looked at videos on Youtube but I still cant seem to grasp it.
Am I right in thinking that the strings will be reversed or is there another way to do it?
Best Answer
HINT: I would simply start from scratch and write down a left-linear grammar directly from the regular expression $b(ab)^*a^*$ that defines the language. Clearly you need $S\to Sa$ and $S\to S_1$, where $S_1$ will ultimately generate strings of the form $b(ab)^*$. You’ll certainly need $S_1\to S_1ab$; can you work out the rest of the productions from here?