2
$\begingroup$

I have a simple grammar as below and wonder if it is convertible to regular grammar?

If yes, what is the conversion sequence? If no, how can we prove it?

S -> A
A -> aAA | b | c

In which S is the start symbol; A is non-terminal; a b c are terminals.

Any help or suggestion is appreciated.

Improve this question
$\endgroup$
  • $\begingroup$ Is the language defined by the grammar regular? If so, you can convert it into a regular grammar. If not, you cannot convert it into a regular grammar. $\endgroup$ – Yuval Filmus Oct 3 '20 at 9:13
  • $\begingroup$ @YuvalFilmus: The language is defined by the grammar in my question. The grammar itself is definitely NOT regular. However, the language defined by the grammar can be regular. $\endgroup$ – mibu Oct 3 '20 at 10:25
  • $\begingroup$ That's what I'm saying – to determine whether your grammar is equivalent to a regular grammar, you have to find out whether the language it generates is regular. $\endgroup$ – Yuval Filmus Oct 3 '20 at 10:26
  • $\begingroup$ @YuvalFilmus: Yeah, that is what I am asking. Currently, I can not prove the language is regular or not? Do you have any suggestions? $\endgroup$ – mibu Oct 3 '20 at 10:28
2
$\begingroup$

You can prove inductively that any word $w$ generated by your grammar satisfies $$\#_b(w) + \#_c(w) = \#_a(w) + 1.$$ Also, you can prove inductively that for every $n$, your grammar generates a word having $a^n$ as a prefix.

You can now use the pumping lemma to show that the language generated by your grammar isn't regular.

Variant: intersect the language generated by your grammar with $a^*b^*$ to get an explicit language which is not regular.

Improve this answer
$\endgroup$
  • $\begingroup$ Wow, that is brilliant. I can work out the problem with your first suggestion. However, I do not quite understand the second one. Could you please elaborate on this? $\endgroup$ – mibu Oct 3 '20 at 11:25
  • 1
    $\begingroup$ You can compare explicitly the intersection of your language with $a^*b^*$ and show that it’s not regular. It follows that your language is also not regular. $\endgroup$ – Yuval Filmus Oct 3 '20 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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