# Transform in linear grammar

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?

• I don't think your grammar is correct, what reasoning did you use to deduce it? May 29 '12 at 23:26
• Your grammar generates $aaaabbaaaa$ which is not generated by the original grammar, but it fails to generate $bbbbaa$ which is generated by the original grammar.
– Raphael
May 30 '12 at 7:36
• Exercise 6.1.a.i, due May 31st, and follow-up on this.
– Raphael
May 30 '12 at 11:29

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?

• I think it is clear that one nonterminal is not enough; you have to separate the $(a\mid c)^*$ and the $(bb)^+$ parts and one nonterminal can not do that.
– Raphael
May 30 '12 at 7:40

It can be useful to first figure out what language the grammar generates and then tailor a grammar. In this case, try and find a (concise) regular expression that describes the generated language.

$(a\mid c)^* (bb)^+ (a\mid c)^2$