TYPES OF GRAMMARS:
Linear and Non Linear
Grammars:
A
grammar is said to be linear if all its productions contain atmost one variable
at the Right Hand Side, otherwise it is a non linear grammar
Example:
(i) S -> aSb
S -> e
Is
a linear grammar
(ii)
S -> Ab
A -> aAb
Is
a linear grammar
(iii) S -> SS
S ->e
Is
a non linear grammar
(iv) S -> aA
A ->b
Is
a non linear grammar
Right Linear Grammar:
A
Grammar is said to be right linear if its productions are of the form
A -> xB
Or
A ->x
Where
A, B are variables and x is a terminal
Example: S -> abS
S -> a
Left Linear Grammar:
A
Grammar is said to be left linear if its productions are of the form
A -> Bx
Or
A ->x
Where
A, B are variables and x is a terminal
Example: S -> Aab
A -> ab/B
Regular Grammar:
A
grammar is said to be regular if it is either right linear or left linear,
otherwise it is a non regular grammar.
Example: S -> abS
S -> a
Example
for Non regular grammar: S ->
aAb
A ->
aS
B ->
a
Recursive Grammar:
A
grammar is said to be recursive if it contains atleast one recursive production
or indirectly recursive production.
Recursive
Production: S -> aS
Indirectly
Recursive Production: S -> aA
A -> abS
No comments:
Post a Comment