retagged by
2,703 views

1 Answer

Best answer
4 votes
4 votes

If a grammar is either left linear (any non-terminal in production comes at the left end) or right linear (any non-terminal in production comes at right end) it is regular

$S\to Sa \mid a$ is left linear so it is regular grammar.

$S\to aS \mid  a$ is right linear, so it is regular grammar.

$S\to SaS \mid a$ is neither left linear nor right linear and hence it is not regular grammar.
 

  • All regular grammars generate regular language
  • Non regular grammar can also generate regular langauge
  • For any regular language, a regular grammar exist
  • A regular grammar cannot generate a non-regular language

In short

A language is regular if and only if  it can be generated by a regular grammar

Related questions

2 votes
2 votes
0 answers
1
shekhar chauhan asked Jul 5, 2016
730 views
Among these languages which is/are Context free Language and has Context Free Grammar ? please Explain the reason a little bit .1 .LISP2 .C-Language3 .C++ Language4 .Cobo...
2 votes
2 votes
1 answer
3
ayushigupta asked Oct 17, 2015
2,130 views
Consider the following CFG$S \to AB$$A \to aBc \mid aB \mid a$$B \to bDe \mid f \mid CD$$C \to Dg \mid h$$D \to g$The rank of the non-terminal $B$ is __________
2 votes
2 votes
3 answers
4