[Solved]: Regular Grammar and Regular Language

Problem Detail: 

My doubt is based on the relation between regular grammar and regular languges

$S \to Sa\ |\ a$ produces the regular language $a^+$ but this grammar is not type-3 grammar of Chomsky classification. So am I correct in stating that this is not a regular grammar even when it produces regular language?

Asked By : Kapes

Answered By : J.-E. Pin

Let me quote the wikipedia entry for linear grammar:

Two special types of linear grammars are the following:

1. the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends
2. the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.

Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

As you can see, your grammar is a left-linear grammar, and it generates a regular language. Type-3 grammars of the Chomsky hierarchy can be defined as right-linear grammars or as left-linear grammars, as you prefer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18503

3.2K people like this

 Download Related Notes/Documents