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

ऑटोमेटा सिद्धांत में, अप्रतिबंधित व्याकरणों का वर्ग (जिसे सेमी-थ्यू, टाइप-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$ परीक्षण किया जाना है, और दूसरे टेप का उपयोग मशीन द्वारा Formal_grammar#Some_mathematical_constructs_regarding_Formal_Grammars उत्पन्न करने के लिए किया जाता है $G$. ट्यूरिंग मशीन तब निम्नलिखित कार्य करती है:

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

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

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

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

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

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

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

यह भी देखें

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