Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation

Unit 3

Grammars

Topic  1  : Types of Grammar in TOC in Hindi  | Chomsky Hierarchy in Theory of Computation

Chomsky Hierarchy  рдХреЗ рдЕрдиреБрд╕рд╛рд░, Grammar рдХреЗ 4 type рд╣реЛрддреЗ рд╣реИрдВ –

1. Type 0 (Recursively enumerable),
2.  Type 1 (Context-sensitive),
3.  Type 2 (Context-free),
4.  Type 3. (Regular Grammar)

рдирд┐рдореНрдирд▓рд┐рдЦрд┐рдд illustration рдкрд░ рдПрдХ рдирдЬрд╝рд░ рдбрд╛рд▓реЗрдВред рдпрд╣ рдкреНрд░рддреНрдпреЗрдХ рдкреНрд░рдХрд╛рд░ рдХреЗ Grammar рдХреЗ scope рдХреЛ рджрд░реНрд╢рд╛рддрд╛ рд╣реИ –

Type-0 grammars :

Type 0 Grammar рдореЗрдВ рд╕рднреА recursively enumerable  рд╢рд╛рдорд┐рд▓ рд╣реИрдВред рд╡реЗ рд╕рднреА Language рдХреЛ рдЙрддреНрдкрдиреНрди рдХрд░рддреЗ рд╣реИрдВ рдЬрд┐рдиреНрд╣реЗрдВ Turing machine рджреНрд╡рд╛рд░рд╛ recognized рдХрд┐рдпрд╛  рд╣реИред рдЗрди Language рдХреЛ recursively enumerable рдпрд╛ Turing-recognizable languages  рдХреЗ рд░реВрдк рдореЗрдВ рднреА рдЬрд╛рдирд╛ рдЬрд╛рддрд╛ рд╣реИред рдзреНрдпрд╛рди рджреЗрдВ рдХрд┐ рдпрд╣ recursive languages рд╕реЗ рдЕрд▓рдЧ рд╣реИ, рдЬрд┐рд╕реЗ рд╣рдореЗрд╢рд╛ рд░реБрдХрдиреЗ рд╡рд╛рд▓реА Turing machine рджреНрд╡рд╛рд░рд╛ рддрдп рдХрд┐рдпрд╛ рдЬрд╛ рд╕рдХрддрд╛ рд╣реИред

Example :

S → ACaB

Bc → acB

CB → DB

aD → Db

Type-1 grammars :

grammars context-sensitive languages generate рдХрд░рддреЗ рд╣реИрдВред productions рдХреЗ рд░реВрдк рдореЗрдВ рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдП

α A β → α γ β

α A β → α γ β

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

String α рдФрд░ β empty рд╣реЛ рд╕рдХрддреЗ рд╣реИрдВ, рд▓реЗрдХрд┐рди non-empty рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдПред

Example :

AB → AbBc 

A → bcA 

B → b

Type - 2 Grammar :  

Type - 2 Grammar  context-free languages  generate рдХрд░рддреЗ рд╣реИрдВред productions A → γ рдХреЗ form рдореЗ рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдпреЗ ред

where A ∈ N (Non terminal)

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

Example :

S → X a 

X → a 

X → aX 

X → abc 

X → ε

Type - 3 Grammar :

Type - 3 Grammar regular languages generate рдХрд░рддреЗ рд╣реИрдВред Type -3 Grammar рдореЗрдВ left-hand side рдПрдХ single non-terminal рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдП рдФрд░ рдПрдХ single terminal рдпрд╛ рдПрдХ single terminal рдХреЗ рдмрд╛рдж right-hand side  рд╕реЗ рдПрдХ рд╣реА terminal рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдПред

productions  X → a or X → aY рдХреЗ form  рдореЗ рд╣реЛрдирд╛ рдЪрд╛рд╣рд┐рдпреЗ

where X, Y ∈ N (Non terminal)

and a ∈ T (Terminal)

Example :

X → ε 

X → a | aY

Y → b