[Solved]: Is this a regular grammar?

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