1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't think your grammar is correct, what reasoning did you use to deduce it? $\endgroup$
    – Sam Jones
    May 29, 2012 at 23:26
  • 2
    $\begingroup$ 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. $\endgroup$
    – Raphael
    May 30, 2012 at 7:36
  • $\begingroup$ Exercise 6.1.a.i, due May 31st, and follow-up on this. $\endgroup$
    – Raphael
    May 30, 2012 at 11:29

2 Answers 2

Reset to default
3
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    May 30, 2012 at 7:40
1
$\begingroup$

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$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.