# Is “A -> aAA” convertible to regular grammar?

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.

• 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. – Yuval Filmus Oct 3 '20 at 9:13
• @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. – mibu Oct 3 '20 at 10:25
• 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. – Yuval Filmus Oct 3 '20 at 10:26
• @YuvalFilmus: Yeah, that is what I am asking. Currently, I can not prove the language is regular or not? Do you have any suggestions? – mibu Oct 3 '20 at 10:28

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.

• 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? – mibu Oct 3 '20 at 11:25
• 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. – Yuval Filmus Oct 3 '20 at 11:26