World's most popular travel blog for travel bloggers.

# [Answers] Transform in linear grammar

, ,
Problem Detail:

i have the following regular grammar : $$S \rightarrow aS | cS | bQ_1$$ $$Q_1 \rightarrow bQ_2$$ $$Q_2 \rightarrow aQ_3 | cQ_3 | bQ_1$$ $$Q_3 \rightarrow aQ_4 | cQ_4$$ $$Q_4 \rightarrow \varepsilon$$

The question is to transform that into a linear grammar with less nonterminals than the regular grammar and my idea was: $$S \rightarrow aSa | cSc | aSc | cSa | bQ_1a | bQ_1c$$ $$Q_1 \rightarrow b$$

and the rest i don't know. Could you help me to solve this problem?

#### Answered By : Sam Jones

Judging from the wording of your question you are still confused about what it means for a grammar to be linear but I wont address that here. If you want to make the grammar smaller you could do the following: remove $Q_4$ from the right hand side of all production rules and remove all rules which start with $Q_4$. You can do this because $Q_4$ doesn't generate anything so it is effectively useless. Next, notice that $Q_1$ serves only to increase the number of $b$'s by one, so you can remove that, too. We can also do a similar trick to remove $Q_3$ as now all $Q_2$ does is give us one of the following strings by rewriting $Q_3$: $$aa, ac, ca, cc$$.

So the resulting grammar looks like this:

$$S \rightarrow aS | cS | bbQ_2$$ $$Q_2 \rightarrow aa | ac | ca | cc | bbQ_2$$.

I'm not claiming that this is the fewest number of non-terminals for this language, maybe you could/should prove that it is/isn't?

###### Best Answer from StackOverflow

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

3.2K people like this