व्याकरण का चॉम्स्की वर्गीकरण

नोम चोमोस्की के अनुसार, व्याकरण के चार प्रकार हैं - टाइप 0, टाइप 1, टाइप 2, और टाइप 3. निम्न तालिका से पता चलता है कि वे एक दूसरे से कैसे भिन्न हैं -

व्याकरण प्रकार	व्याकरण स्वीकृत	भाषा स्वीकृत	आटोमैटिक मशीन
टाइप ०	अप्रतिबंधित व्याकरण	पुनरावर्ती भाषा	ट्यूरिंग मशीन
श्रेणी 1	प्रसंग-संवेदी व्याकरण	प्रसंग-संवेदी भाषा	रैखिक-बंधे ऑटोमेटन
टाइप 2	प्रसंग-मुक्त व्याकरण	प्रसंग-मुक्त भाषा	पुशडाउन ऑटोमेटन
टाइप 3	नियमित व्याकरण	नियमित भाषा	परिमित राज्य ऑटोमेटन

निम्नलिखित दृष्टांत पर एक नज़र डालें। यह प्रत्येक प्रकार के व्याकरण के दायरे को दर्शाता है -

प्रकार - 3 व्याकरण

Type-3 grammarsनियमित भाषा उत्पन्न करें। टाइप -3 व्याकरण में बाएं हाथ की ओर एक एकल गैर-टर्मिनल और एक एकल टर्मिनल या एक एकल टर्मिनल के बाद दाएं हाथ से युक्त एक टर्मिनल होना चाहिए।

प्रस्तुतियों के रूप में होना चाहिए X → a or X → aY

कहाँ पे X, Y ∈ N (गैर टर्मिनल)

तथा a ∈ T (टर्मिनल)

नियम S → ε अनुमति है अगर S किसी नियम के दाईं ओर दिखाई नहीं देता है।

उदाहरण

X → ε 
X → a | aY
Y → b

प्रकार - 2 व्याकरण

Type-2 grammars संदर्भ-मुक्त भाषाएं उत्पन्न करें।

प्रस्तुतियों के रूप में होना चाहिए A → γ

कहाँ पे A ∈ N (गैर टर्मिनल)

तथा γ ∈ (T ∪ N)* (टर्मिनलों और गैर-टर्मिनलों का स्ट्रिंग)।

इन व्याकरणों द्वारा उत्पन्न इन भाषाओं को एक गैर-नियतात्मक पुशडाउन ऑटोमेटन द्वारा मान्यता प्राप्त है।

उदाहरण

S → X a 
X → a 
X → aX 
X → abc 
X → ε

प्रकार - 1 व्याकरण

Type-1 grammarsसंदर्भ-संवेदनशील भाषाएं उत्पन्न करें। प्रस्तुतियों के रूप में होना चाहिए

α A β → α γ β

कहाँ पे A ∈ N (गैर-टर्मिनल)

तथा α, β, γ ∈ (T ∪ N)* (टर्मिनलों और गैर-टर्मिनलों के तार)

तार α तथा β खाली हो सकता है, लेकिन γ खाली नहीं होना चाहिए।

नियम S → εअनुमति दी जाती है यदि S किसी नियम के दाईं ओर दिखाई नहीं देता है। इन व्याकरणों द्वारा उत्पन्न भाषाओं को एक रेखीय बंधित ऑटोमेटन द्वारा मान्यता प्राप्त है।

उदाहरण

AB → AbBc 
A → bcA 
B → b

प्रकार - ० व्याकरण

Type-0 grammarsपुनरावर्ती असंख्य भाषाएं उत्पन्न करते हैं। प्रस्तुतियों पर कोई प्रतिबंध नहीं है। वे सभी औपचारिक व्याकरणों सहित किसी भी चरण संरचना व्याकरण हैं।

वे उन भाषाओं को उत्पन्न करते हैं जो एक ट्यूरिंग मशीन द्वारा मान्यता प्राप्त हैं।

प्रस्तुतियों के रूप में हो सकता है α → β कहाँ पे α कम से कम एक गैर-टर्मिनल और टर्मिनलों के साथ टर्मिनलों की एक स्ट्रिंग है α रिक्त नहीं हो सकता। β टर्मिनलों और गैर-टर्मिनलों की एक स्ट्रिंग है।

उदाहरण

S → ACaB 
Bc → acB 
CB → DB 
aD → Db