Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?.

share|cite|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|cite|improve this answer
I got that. But according to [wikipedia][], a regular grammar is a formal grammar that describes a regular language. Now, my grammar is describing a regular language. The set of rules are mentioned later, not as definition. – Shashwat Dec 18 '12 at 11:56
@Shashwat: You referring to a property of a regular grammar (it accepts a regular language), but this is not the definition of a regular language. The definition goes over the restricted left hand sides of the rules. – A.Schulz Dec 18 '12 at 13:29
As the above comment says, the statement "a regular grammar is a formal grammar that describes a regular language" is not the definition of a regular grammar. That wikipedia page doesn't explicitly use the word definition at all. A better place to learn the basics and formal definitions would be a textbook. My favourite is… – Sam Jones Dec 18 '12 at 14:13
Ok. If restriction of rules is the definition, then my doubt is cleared. The on wikipedia, that was the first line; so I assumed it to be the definition. Thank you. – Shashwat Dec 18 '12 at 17:05
I just fixed the wording in Wikipedia. – reinierpost Jan 19 at 7:46

This a type-2 grammar (CFG) not type-3 (regular garmmar), because it consists of both left hand derivation and right hand derivation. There are CFGs which generate regular languages. That's a property.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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