[Solved]: generation of linear grammar

Problem Detail: 

We have the following linear grammar: $$E \rightarrow aO | bO | bbE | bb$$ $$O \rightarrow aE | bE | abaE | aba$$ Does the linear grammar generate a regular language, if yes why ? Our alphabet is $\Sigma$ = {a,b} and our nonterminals are E and O. We begin by E.

Asked By : user1594

Answered By : Patrick87

Yep, this generates a regular language. We can show this fairly easily by constructing an equivalent regular grammar. We start with

$$E \rightarrow aO | bO | bbE | bb$$ $$O \rightarrow aE | bE | abaE | aba$$

Introduce new nonterminal symbols as follows:

$$V \rightarrow bE | b$$ $$W \rightarrow bX$$ $$X \rightarrow aE | a$$

Then we can rewrite the rules for $E$ and $O$ as

$$E \rightarrow aO | bO | bV$$ $$O \rightarrow aE | bE | aW$$

Now the rules for $E, O, V, W, X$ are such that (a) they produce the same language as the linear grammar and (b) they constitute a regular grammar. Since regular grammars produce regular languages, you're done. Also see the Wikipedia entry for Regular Grammars; a right-regular grammar is given above. To see that it generates the same language as the linear grammar, notice that $V, W, X$ can be eliminated via substitution to recover the original.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2166

3.2K people like this

 Download Related Notes/Documents