Problem Detail: I went through a question asking me to categorize the following grammar. $$S → AA, S → AB, A → a, A→BB, B → b, B → e$$ From the production rules, clearly it is Context-Free. But it accepts a finite set of strings. ${e, a, aa, ab, abb, ba, bba, b, bb, bbb, bbbb}$ which is regular language. So, is the above grammar regular? Though it does not follow from the rules. Basically my question is: Is the grammar ${S → AA, A → a}$ regular?.
Asked By : Shashwat
Answered By : Sam Jones
The answer is no. Whilst the language is finite and therefore regular the grammar itself is not regular. I think you already knew this as you said that this grammar’s production rules are not of the form of a regular grammar. The point here is that just because a grammar isn’t regular doesn’t mean the language it generates must not be regular.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7486 Ask a Question Download Related Notes/Documents
