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 -&gt; A
A -&gt; 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.
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.