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

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

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

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

कम्प्यूटेशनल गुण

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

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

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

यह भी देखें

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