Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation
Computer Science Engineering Tutorials in Hindi | Theory of ComputationUnit 3
Grammars
Topic 1 : Types of Grammar in TOC in Hindi | Chomsky Hierarchy in Theory of Computation
Chomsky Hierarchy के अनुसार, Grammar के 4 type होते हैं –
- Type 0 (Recursively enumerable),
- Type 1 (Context-sensitive),
- Type 2 (Context-free),
- Type 3. (Regular Grammar)
|
|
|
Automaton | |||
| Type 0 |
|
|
|
|||
| Type 1 |
|
|
|
|||
| Type 2 |
|
|
|
|||
| Type 3 |
|
|
|
निम्नलिखित 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
