TYPES OF GRAMMAR IN T.O.C.

 According to Noam Chomsky, there are four types of grammars − Type 0, Type 1, Type 2, and Type 3. Let's see them one by one.

Grammar Type	Grammar Accepted	Language Accepted	Automaton
Type 0	Unrestricted grammar	Recursively enumerable language	Turing Machine
Type 1	Context-sensitive grammar	Context-sensitive language	Linear-bounded automaton
Type 2	Context-free grammar	Context-free language	Pushdown automaton
Type 3	Regular grammar	Regular language	Finite state automaton

Take a look at the following illustration. It shows the scope of each type of grammar −

Type 0 grammar:-

Also known as unrestricted grammar generate recursively enumerable languages. The productions have no restrictions. They are any phase structure grammar including all formal grammars.

They generate the languages that are recognized by a Turing machine. A Turning Machine can simulate an Unrestricted Grammar and an Unrestricted Grammar can simulate Turning Machine configurations. It can always be found for the language recognized or generated by any Turning Machine

The productions can be in the form of α → β where α is a string of terminals and nonterminals with at least one non-terminal and α cannot be null. β is a string of terminals and non-terminals.

Example:-

Language--> L={anbncn | n≥0}

Grammar--> S→aBSc {Equal Number of a's, B's, c's} S→ ε {Eliminate S} Ba→aB {Move a's to Right of B's} Bc→bc {Reduce B before first c to b} Bb→bb {Reduce all remaining B's to b

Type 1 grammar:-

Also known as Context-sensitive grammar generate context-sensitive languages. The productions must be in the form

α A β → α γ β

where A ∈ N (Non-terminal)

and α, β, γ ∈ (T ∪ N)* (Strings of terminals and non-terminals)

The strings α and β may be empty, but γ must be non-empty.

The rule S → ε is allowed if S does not appear on the right side of any rule. The languages generated by these grammars are recognized by a linear bounded automaton.

Example:-

Consider the following CSG.

S → abc/aAbc
Ab → bA
Ac → Bbcc
bB → Bb
aB → aa/aaA

The language generated by this grammar is:-

S → aAbc
→ abAc
→ abBbcc
→ aBbbcc
→ aaAbbcc
→ aabAbcc
→ aabbAcc
→ aabbBbccc
→ aabBbbccc
→ aaBbbbccc
→ aaabbbccc

--in general {anbncn | n≥1}.

Type 2 grammar:-

Also known as Context-free grammar generates context-free languages.

The productions must be in the form A → γ

where A ∈ N (Non terminal)

and γ ∈ (T ∪ N)* (String of terminals and non-terminals).

These languages generated by these grammars are be recognized by a non-deterministic pushdown automaton.

Example:-

Grammar->  S-->aS/ε

Language->  a* (string contains number of 'a' many times)

 S  
-aS   
-aaS         
-aaaS         
-aaaaS        
-aaaaaS        
-aaaaaaS       
-aaaaaaε       
-aaaaaa

Type 3 grammar:- 

Also known as Regular grammar generate regular languages. Type-3 grammars must have a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal or single terminal followed by a single non-terminal.

The productions must be in the form X → a or X → aY

where X, Y ∈ N (Non terminal)

and a ∈ T (Terminal)

The rule S → ε is allowed if S does not appear on the right side of any rule.

Example:-

Grammar:-

X→ε 

X→a/aY

Y→b

Language that will produce will be:- ^+a+ab+b

i.e. X--> a (produce 'a' only) or X-->ab(by replacing Y with 'b')

or if X produces null(nothing) then alone Y will  give 'b' as a string

so the entire production rule will produce either null string or 'a' or 'b' or may be 'ab'

here '+' sign indicates the 'or' condition or '^' indicates the null production.