Chomsky Hierarchy of Grammars | चॉम्स्की व्याकरण पदानुक्रम

औपचारिक भाषा सिद्धांत (Formal Language Theory) में Chomsky Hierarchy एक महत्वपूर्ण मॉडल है जिसे Noam Chomsky ने 1956 में प्रस्तावित किया था। इस Hierarchy में सभी प्रकार की Grammars और उनकी संबंधित भाषाओं (Languages) को उनके computational power के आधार पर चार श्रेणियों में बाँटा गया है — Type-0, Type-1, Type-2, और Type-3।

परिचय / Introduction

Chomsky Hierarchy भाषाओं और उनके संबंधित Automata के बीच संबंध को समझाती है। यह दिखाती है कि कुछ भाषाएँ सरल मशीनों (जैसे Finite Automata) द्वारा पहचानी जा सकती हैं, जबकि कुछ के लिए अधिक जटिल मशीनों (जैसे Turing Machine) की आवश्यकता होती है।

1️⃣ चार प्रकार की Grammars / Four Types of Grammars

Chomsky Hierarchy में Grammars को निम्न चार प्रकारों में वर्गीकृत किया गया है:

Grammar Type	Language Type	Recognized By	Production Rule Form
Type 0	Recursively Enumerable Languages	Turing Machine	α → β
Type 1	Context-Sensitive Languages	Linear Bounded Automata	αAβ → αγβ (|αγβ| ≥ |αAβ|)
Type 2	Context-Free Languages	Pushdown Automata	A → α
Type 3	Regular Languages	Finite Automata	A → aB | a

2️⃣ Type 3 Grammar: Regular Grammar / रेगुलर व्याकरण

Regular Grammar सबसे सरल Grammar होती है जो Regular Languages को generate करती है। इसे Finite Automata द्वारा recognize किया जा सकता है।

Rule Form:

A → aB या A → a

Example:

S → aA | bB
A → aA | a
B → bB | b

3️⃣ Type 2 Grammar: Context-Free Grammar (CFG) / प्रसंग-मुक्त व्याकरण

Context-Free Grammar वह Grammar है जिसमें प्रत्येक Production Rule का Left-hand Side केवल एक Non-terminal होता है। यह Pushdown Automata द्वारा स्वीकार की जाती है।

Rule Form:

A → α

Example:

S → aSb | ε

Language: {aⁿbⁿ | n ≥ 0}

4️⃣ Type 1 Grammar: Context-Sensitive Grammar (CSG) / प्रसंग-संवेदनशील व्याकरण

यह Grammar अधिक शक्तिशाली होती है। यह उन भाषाओं को generate करती है जिन्हें Linear Bounded Automata (LBA) पहचानती हैं।

Rule Form:

αAβ → αγβ जहाँ |αγβ| ≥ |αAβ|

Example:

S → aSBC | abc
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

Language: {aⁿbⁿcⁿ | n ≥ 1}

5️⃣ Type 0 Grammar: Unrestricted Grammar / अप्रतिबंधित व्याकरण

यह सबसे सामान्य Grammar होती है जिसमें कोई प्रतिबंध नहीं होता। यह Turing Machine द्वारा पहचानी जाती है।

Rule Form:

α → β जहाँ α में कम-से-कम एक Non-terminal होता है।

Example:

S → aSb | SS | ε

6️⃣ Hierarchical Relationship / पदानुक्रम संबंध

इन सभी Grammar Types के बीच एक क्रमिक संबंध होता है:

Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0

इसका अर्थ है कि:

• हर Regular Language एक Context-Free Language भी है।
• हर Context-Free Language एक Context-Sensitive Language है।
• हर Context-Sensitive Language एक Recursively Enumerable Language है।

7️⃣ Chomsky Hierarchy का चित्रण / Diagram Representation

        Type 0 (Recursively Enumerable)
        ┌───────────────────────────────┐
        │   Type 1 (Context-Sensitive)  │
        │   ┌───────────────────────────┐
        │   │  Type 2 (Context-Free)   │
        │   │   ┌──────────────────────┐
        │   │   │ Type 3 (Regular)    │
        │   │   └──────────────────────┘
        │   └───────────────────────────┘
        └───────────────────────────────┘

8️⃣ Comparison Table / तुलना सारणी

Grammar Type	Example Language	Recognized By	Power
Type 0	{aⁿbⁿcⁿdⁿ | n ≥ 1}	Turing Machine	Highest
Type 1	{aⁿbⁿcⁿ | n ≥ 1}	Linear Bounded Automata	High
Type 2	{aⁿbⁿ | n ≥ 0}	Pushdown Automata	Moderate
Type 3	{aⁿ | n ≥ 0}	Finite Automata	Lowest

9️⃣ व्यावहारिक उपयोग / Applications

• Compiler Design में विभिन्न स्तरों के Syntax Analysis के लिए।
• Machine Learning में Language Classification के लिए।
• AI में Natural Language Understanding के लिए।
• Formal Verification और Language Processing में।

🔟 निष्कर्ष / Conclusion

Chomsky Hierarchy औपचारिक भाषाओं और उनके computational models के बीच एक पुल का कार्य करती है। यह दिखाती है कि जैसे-जैसे Grammar की जटिलता बढ़ती है, उसे पहचानने वाली मशीन की शक्ति भी बढ़ती है। Regular Grammar सबसे सरल और Turing Machine सबसे शक्तिशाली होती है। यह Hierarchy Compiler Design, AI, और Natural Language Processing जैसे क्षेत्रों में अत्यंत उपयोगी है।