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?

• 1. You asked an extremely similar question just 10 hours ago: cs.stackexchange.com/q/44161/755. Please don't re-post the same question (and have some patience; it sometimes take a little while for people to see your question and answer it). 2. If you want to ask in general rather than about this specific grammar, then this is already covered by our reference questions. Please take the time to search on this site and in standard resources before asking here, and show us what research you've done in the question. – D.W. Jul 6 '15 at 3:06
• Well if I didn't ask this question I would be still thinking I was right and that would be bad going forward. Instead thanks to Mr Decker now I have learn something isn't this the purpose of this site? The other question is quite different (and in fact the answer present another methodology non quite applicable here). – Crysis85 Jul 6 '15 at 7:34

1 Answer

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.