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)

 

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

 

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

 

निम्नलिखित 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

Related Post