अनरिस्ट्रिक्टेड ग्रामर

ऑटोमेटा सिद्धांत में अनरिस्ट्रिक्टेड ग्रामर क्लास (जिसे सेमी-थ्यू, टाइप-0 या फ्रेज स्ट्रक्चर ग्रामर भी कहा जाता है) चॉम्स्की हायरार्की में ग्रामर की यह सबसे सामान्य क्लास है। अनरिस्ट्रिक्टेड ग्रामर के निर्माण पर कोई प्रतिबंध नहीं लगाया गया है क्योकि अनरिस्ट्रिक्टेड ग्रामर की प्रत्येक बायी क्लास गैर-रिक्त होती है। सामान्यतः यह ग्रामर क्लास अपेक्षाकृत रूप से रिकर्सिवली एनयूमेरबल भाषाएँ उत्पन्न कर सकती है।

औपचारिक परिभाषा

अनरिस्ट्रिक्टेड ग्रामर एक औपचारिक ग्रामर ${\textstyle G=(N,T,P,S)}$ है, जहां

• $N$ गैर-टर्मिनल प्रतीक का एक सीमित समूह है।
• $T$, $N$ और $T$ डिसजोईन्ट के साथ टर्मिनल प्रतीकों का एक सीमित समूह है।
• $P$ बीटा के कंप्यूटर उत्पादन नियमों का एक सीमित समूह $\alpha \to \beta$ है। $\alpha$ और $\beta$, $N\cup T$ में प्रतीकों की स्ट्रिंग हैं, जहां $\alpha$ रिक्त स्ट्रिंग नहीं है।

• $S\in N$ एक विशेष रूप से नामित प्रारम्भिक प्रतीक है।

जैसा कि नाम से पता चलता है कि अनरिस्ट्रिक्टेड ग्रामर के उत्पादन नियमों के प्रकारों पर कोई वास्तविक प्रतिबंध नहीं होता है।

ट्यूरिंग मशीनों के समतुल्य

अनरिस्ट्रिक्टेड ग्रामर रिकर्सिवली एनयूमेरबल भाषाओं की विशेषता बताती है। यह कहने के लिए सामान्य है कि प्रत्येक अनरिस्ट्रिक्टेड ग्रामर $G$ के लिए कुछ ट्यूरिंग मशीने सम्मिलित हैं जो इसके विपरीत $L(G)$ को पहचानने में सक्षम हैं। अनरिस्ट्रिक्टेड ग्रामर को देखते हुए, ऐसी ट्यूरिंग मशीन दो-टेप डेटर्मिनिस्टिक ट्यूरिंग मशीन के रूप में बनाने के लिए अपेक्षाकृत सरल है। पहले टेप में परीक्षण के लिए इनपुट शब्द $w$ होता है और दूसरे टेप का उपयोग मशीन द्वारा $G$ से सिन्टेक्स को उत्पन्न करने के लिए किया जाता है। जिससे ट्यूरिंग मशीन प्रायः निम्नलिखित कार्य करती है:

1. दूसरे टेप के बाईं ओर से प्रारंभ करें और बार-बार दाईं ओर जाने का चयन करें या टेप पर वर्तमान स्थिति का चयन करें।
2. $G$ प्रस्तुतियों में से डेटर्मिनिस्टिक एल्गोरिदम $\beta \to \gamma$ को चुनें।
3. यदि $\beta$ दूसरे टेप पर किसी स्थान पर दिखाई देता है, तो उस बिंदु पर $\beta$ को $\gamma$ से परिवर्तित करें, संभवतः $\beta$ और $\gamma$ की सापेक्ष लंबाई के आधार पर टेप पर प्रतीकों को बाएं या दाएं स्थानांतरित करें। उदाहरण के लिए यदि $\beta$, $\gamma$ से लंबा है, तो टेप को स्थानांतरित करें।
4. टेप 2 पर परिणामी सिन्टेक्स की तुलना टेप 1 पर टेक्स्ट से करें। यदि वे समान हैं, तो ट्यूरिंग मशीन टेक्स्ट को स्वीकृत कर लेती है। यदि वे ऐसा नहीं करती है, तो ट्यूरिंग मशीन टेप 1 पर वापस चली जाती है।

यह देखना आसान है कि यह ट्यूरिंग मशीन अंतिम टेप को अपेक्षाकृत रूप से कई बार कार्यान्वित करने के बाद अपने दूसरे टेप पर $G$ के सभी और केवल टेक्स्ट रूपों को उत्पन्न उत्पन्न करती है। इस प्रकार भाषा $L(G)$ को रिकर्सिवली एनयूमेरबल भाषा के रूप मे माना जा सकता है।

इसके विपरीत निर्माण भी संभव है यदि कुछ ट्यूरिंग मशीन को देखते हुए, एक समतुल्य अनरिस्ट्रिक्टेड ग्रामर बनाना संभव है जो केवल बायीं ओर एक या एक से अधिक गैर-टर्मिनल प्रतीकों वाली प्रस्तुतियों का उपयोग करता है। इसलिए एक अपेक्षाकृत अनरिस्ट्रिक्टेड ग्रामर को सदैव ट्यूरिंग मशीन में परिवर्तित करके और फिर से बाद वाले फॉर्म का उपयोग करने के लिए समान रूप से परिवर्तित किया जा सकता है। कुछ लेखक अनरिस्ट्रिक्टेड ग्रामर की परिभाषा के रूप में भी इसका उपयोग करते हैं।

कम्प्यूटेशनल विशेषताएँ

किसी दी गई स्ट्रिंग को किसी अनरिस्ट्रिक्टेड ग्रामर द्वारा उत्पन्न किया जा सकता है या नहीं उत्पन्न किया जा सकता है। इसकी निर्णय समस्या इस समस्या के बराबर है कि क्या इसे ग्रामर के समकक्ष ट्यूरिंग मशीन द्वारा स्वीकृत किया जा सकता है। बाद वाली समस्या को हॉल्टिंग समस्या कहा जाता है और सामान्यतः यह अनडिसाइडेबल (अनिर्णनीय) है।

रिकर्सिवली एनयूमेरबल भाषाएं क्लेन स्टार, कॉन्सटेनेशन, यूनियन और इंटरसेक्शन के अंतर्गत क्लोजर हैं। जिसके लिए रिकर्सिवली एनयूमेरबल भाषा क्लोजर गुण देखें।

ट्यूरिंग मशीनों के लिए अनरिस्ट्रिक्टेड ग्रामर की समानता एक सार्वभौमिक अनरिस्ट्रिक्टेड ग्रामर के अस्तित्व को दर्शाती है। एक ग्रामर भाषा का विवरण दिए जाने पर अन्य अनरिस्ट्रिक्टेड ग्रामर भाषाएं विवरण को स्वीकृत करने में सक्षम होती हैं। इस कारण से अनरिस्ट्रिक्टेड ग्रामर जैसे थ्यू (प्रोग्रामिंग भाषा) के आधार पर एक प्रोग्रामिंग भाषा बनाना सैद्धांतिक रूप से संभव है।

यह भी देखें

• लैम्ब्डा कैलकुलस
• सेमी-थू सिस्टम - टर्मिनल और नॉनटर्मिनल प्रतीकों में अंतर नहीं करता है और रिक्त बाएं क्लास को स्वीकृत करता है।