2,263 views
2 votes
2 votes
If any grammer is given, how can we tell that the grammar is regular or not? Is that any perticular method?

2 Answers

2 votes
2 votes

Regular Grammar -:Type 3 Grammar and is of the form 

             $1.S\rightarrow aA\,$

            $1.S\rightarrow Aa\,$

Where $A,S \, \epsilon $ $Non\:Terminal$,

$a\epsilon\: Terminal$, But  NOT the combination of both.

eg-:

consider Production

$S\rightarrow aA$(right Linear/Regular Grammar)

$A\rightarrow Ab$(left Linear/Regular Grammar)

$A\rightarrow\varepsilon$

is not a regular grammar as it contains both Left and Right linear Grammar.

0 votes
0 votes

there simple point to check wether the grammar is regular or not 

first point . If given grammar contain two or more than two non terminal  in the right hand side of production than the grammar will not  regular grammar 

second point. a regular language can have more than one grammar which can be regular or not regular 

take an example of regular language (a+b)(a+b)+

and grammar

S->AA

A->aA | bA | a | b 

here the language is regular but the grammar is not regular 

but you can generate at least one regular grammar for this language 

conclusion we can generate at least one regular grammar for every regular language 

third point . If grammar has production which  is either left linear or right linear but not both the the grammar is a regular grammar 
edited by

Related questions

2 votes
2 votes
1 answer
3