FOR FREE YEAR SOLVED
TYPES OF GRAMMAR
As per Chomsky classification, there are three types of grammar:
Type 0, Type 1, Type 2 and Type 3.
Type 0: This grammar is called Phrase Structure Grammar (PSG) or Unrestricted Grammar; it is called unrestricted because it is the highest degree of grammar with no restriction.
General definition of Type 0 grammar:
.png)
[left-hand side of the production can contain variables (non-terminal) and terminals but not empty symbols (λ) and right-hand side of the production can contain variables and terminals including empty symbols (λ)]
Examples:
S → Aba | λ
aS → aAb
AB → CB
Language: Language of this grammar is Recursively Enumerable Language.
Machine: Turing Machine.
Type 1: This grammar is called non-contracting grammar or Context Sensitive Grammar.
Definition of Context Sensitive Grammar:
G = (V, T, S, P)
V is a finite set of symbols called the variables (Non-terminals);
T is the set of terminal symbols;
S ∊ V is a designated symbol called the start symbol;
P: αAβ → αγβ, with A ∊ V (Non-terminals), or S → λ,
And if S → λ ∊ P, then S does not appear on the right-hand side of any production.
Examples:
S → cD
aA → aBb
SA → CB
Language: Language of this grammar is Context Sensitive Language.
Machine: Language of this grammar is Linear Bounded Automata.
Type 2: This grammar is called Context Free Grammar.
Definition of Context Free Grammar:
G = (V, T, S, P)
V is a finite set of symbols called the variables (Non-terminals);
T is the set of terminal symbols;
S ∊ V is a designated symbol called the start symbol;
P: V → (V ∪ T)* [Right hand side of the production V has no left or right context]
Let αAβ is string here α is left context and β is right context. λAλ, here no left and right context.
(λ.A = A.λ = A).
This grammar is called context free grammar because Right hand side of the production V has left or right context-free.
Examples:
S → cD | λ
A → aBb
B → CB
Language: Context Free Language
Machine: Pushdown Automata (PDA)
Note: This is very important grammar for us because generally, we are working with context-free grammar.
Type 3: This grammar is called Regular grammar or Finite State Grammar.
Definition of Regular Grammar:
G = (V, T, S, P)
V is a finite set of symbols called the variables (Non-terminals);
T is the set of terminal symbols;
S ∊ V is a designated symbol called the start symbol;
P: V → T*|T*V (Right linear)
V → T*|VT* (Left linear)
We can write this product more simple way like V → T* or V → T*V or V → VT*.
A Regular grammar is one that is either right linear or left linear but not both.
Note: What is Linear: ax + b is linear but is non-linear because it has the power of x (variable). xy + 6 = 0 is non-linear because it has two variables, linear means only one variable will be there (Single).
Examples:
S → a | λ
A → aA ( right linear)
C → Caa (left linear)
B → abba
Language: Regular Language or Finite State Language
Machine: Finite Automata
.png)
