CODEWITHSUNDEEP
grammarregular-language
Ramy Al Zuhouri
Ramy Al Zuhouri

Reputation: 21966

Difference between a regular language and a regular grammar

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.

Upvotes: 4

Views: 11078

Answers (3)

Savannah Madison
Savannah Madison

Reputation: 657

I think if I explain the difference between a language and grammar, your queries will automatically get resolved.

A language is a set of strings over some set of alphabets satisfying certain rules encoded as grammars, while Grammars are used to generate languages.

So basically grammars denote the syntactical rules of a string and the set of strings that can be generated with the start symbol of the grammar is called the Language of the grammar

Upvotes: 0

buc
buc

Reputation: 6358

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.

Upvotes: 4

NPE
NPE

Reputation: 500297

A formal grammar is a set of rules, whereas a formal language is a set of strings.

A regular grammar is a formal grammar that describes a regular language.

According to Wikipedia:

[T]he left regular grammars generate exactly all regular languages. The right regular grammars describe the reverses of all such languages, that is, exactly the regular languages as well.

If mixing of left-regular and right-regular rules is allowed, we still have a linear grammar, but not necessarily a regular one.

In the above, left-regular rules are rules of the form V->Wa (right-regular, of the form V->aW).

Upvotes: 2

Related Questions