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?
Transform in linear grammar
formal grammars
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?