Difference between a regular language and a regular grammar

grammar regular-language
Ramy Al Zuhouri picture Ramy Al Zuhouri · Feb 5, 2012 · Viewed 7.5k times · Source

My book gives similar but slightly different explanations of regular grammar and regular language. I doubt it's wrong, is a regular language the same thing of a regular grammar? The definition of my book is: A grammar is regular if all the productions are V-> aW or V->Wa with V,W non terminal or terminal symbols, "a" terminal symbol.W can also be empty or be the same of V.

Answer

buc picture buc · Feb 5, 2012

Regular grammars and regular languages are two different terms:

  1. A language is a (possibly infinite) set of valid sequences of terminal symbols.
  2. A grammar defines which are the valid sequences.

The same language could be represented with different class of grammars (regular, context free, etc.). A language is said to be regular if it can be represented with a regular grammar. On the othet hand, a regular grammar always defines a regular language. What you have posted is the definition of the regular grammar.

See this Wikipedia post for further information.

Related questions

Left-Linear and Right-Linear Grammars

I need help with constructing a left-linear and right-linear grammar for the languages below? a) (0+1)*00(0+1)* b) 0*(1(0+1))* c) (((01+10)*11)*00)* For a) I have the following: Left-linear S --> B00 | S11 B --> B0|B1|011 Right-linear S --> 00B | 11S …

Read More
How to identify whether a grammar is LL(1), LR(0) or SLR(1)?

How do you identify whether a grammar is LL(1), LR(0), or SLR(1)? Can anyone please explain it using this example, or any other example? X → Yz | a Y → bZ | ε Z → ε

Read More
What is the difference between LR, SLR, and LALR parsers?

What is the actual difference between LR, SLR, and LALR parsers? I know that SLR and LALR are types of LR parsers, but what is the actual difference as far as their parsing tables are concerned? And how to show …

Read More