# Regular Expression from Context Free Grammar [duplicate]

The purpose of this exercise is to write a program that recognize all the words derived from this grammar. The time complexity of this program must be O(n) hence i must be able to derive a regular expression from the grammar

$S\rightarrow ASA\mid A$
$A\rightarrow aAa\mid aAab\mid bA\mid\epsilon$

By intuition I guessed that this grammar generates words in the form of $\left \{ a^ia^jb^*a^jb^ja^i \right \}^*$ and, correct me if I'm wrong, this doesn't seems like a regular language.

My problem with this type of exercise (I've tried a lot like this) is that there is no automatic way to find the regular expression from the grammar even if it generates indeed a regular language. Any advice on how to proceed on exercises like this?

## marked as duplicate by D.W.♦, Luke Mathieson, Juho, David Richerby, vonbrandJul 8 '15 at 23:13

Denote your grammar by $G$ and let $$M=\{w\in\{a,b\}^*\mid |w|_a\equiv 0\pmod 2\}$$ where $|w|_a$ is the number of $a$s in $w$. In other words, $M$ is the set of all strings of $a$s and $b$s with an even number of $a$s. We claim $L(G)=M$.
First, it is clear that any word in $L(G)$ must have an even number of $a$s, so $L(G)\subseteq M$. All we now have to do is show $M\subseteq L(G)$, in other words, that every string in $M$ can be generated by $G$. We'll show this by induction on the number, $n$, of $a$s in a word.
If $n=0$, we can generate strings consisting only of $i\ge 0\ b$s by one of two derivations: \begin{align} S &\Rightarrow A\Rightarrow \epsilon \\ S &\Rightarrow A\Rightarrow bA\stackrel{*}{\Rightarrow} b^i \end{align} So we can generate all strings with no $a$s.
If $n=2$, any string in $M$ with exactly two $a$s must have the form $b^iab^jab^k$ with $i, j, k\ge 0$. Write such a string as $(b^i)(ab^ja)(b^k)$. We've seen that we can generate the $b^i$ and $b^k$ portions from $A$. We can also generate the $ab^ja$ part from $A$: $$A\Rightarrow aAa\stackrel{*}{\Rightarrow} ab^ja$$ so we can generate $b^iab^jab^k$ by $$S\Rightarrow ASA\Rightarrow AAA\stackrel{*}{\Rightarrow} b^iAA\stackrel{*}{\Rightarrow}b^iab^jaA\stackrel{*}{\Rightarrow}b^iab^jab^k$$ and it's clear that we can continue this process for even $n>2$, simply by starting with the requisite number of $A$s. In short, we've shown that any word in $M$ can be generated by the grammar $G$, and this, combined with the first part, shows that $L(G)=M$.
Of course, $M$ is regular, if for no other reason than it is denoted by the regular expression $(ab^*a+b)^*$. Also, it would also be easy to construct a finite automaton for $L$ as well.