2
$\begingroup$

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

Improve this question
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I got that. But according to [wikipedia][en.wikipedia.org/wiki/Regular_grammar], 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. $\endgroup$
    – Shashwat
    Dec 18 '12 at 11:56
  • 1
    $\begingroup$ @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. $\endgroup$
    – A.Schulz
    Dec 18 '12 at 13:29
  • $\begingroup$ 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 en.wikipedia.org/wiki/… $\endgroup$
    – Sam Jones
    Dec 18 '12 at 14:13
  • $\begingroup$ 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. $\endgroup$
    – Shashwat
    Dec 18 '12 at 17:05
  • 2
    $\begingroup$ I just fixed the wording in Wikipedia. $\endgroup$
    – reinierpost
    Jan 19 '15 at 7:46
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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