ट्यूरिंग मशीन - ट्यूरिंग मशीन एक ऐसा उपकरण है जिसका उपयोग टाइप 0 व्याकरण द्वारा उत्पन्न भाषा के शब्दों को स्वीकार करने के लिए किया जाता है। एक ट्यूरिंग मशीन (टीएम) एक गणितीय मॉडल है जिसमें एक अनंत लंबाई का टेप होता है जो कोशिकाओं में विभाजित होता है जिस पर इनपुट दिया जाता है। इसमें एक हेड होता है जो इनपुट टेप को पढ़ता है। एक राज्य रजिस्टर ट्यूरिंग मशीन की स्थिति को संग्रहीत करता है। एक इनपुट सिंबल को पढ़ने के बाद, इसे दूसरे सिंबल से बदल दिया जाता है, इसकी आंतरिक स्थिति बदल दी जाती है, और यह एक सेल से दाएं या बाएं ओर चला जाता है। यदि TM अंतिम अवस्था में पहुँच जाता है, तो इनपुट स्ट्रिंग को स्वीकार कर लिया जाता है, अन्यथा अस्वीकार कर दिया जाता है।
एक TM को औपचारिक रूप से 7-टुपल (Q, X, Σ, δ, q0, B, F) के रूप में वर्णित किया जा सकता है, जहां -
- Q राज्यों का एक सीमित समूह है
- X टेप वर्णमाला है
- Σ इनपुट वर्णमाला है
- δ एक संक्रमण फलन है; :क्यू × एक्स → क्यू × एक्स × {लेफ्ट_शिफ्ट, राइट_शिफ्ट}।
- q0 प्रारंभिक अवस्था है
- B रिक्त प्रतीक है
- F अंतिम अवस्थाओं का समुच्चय है
हमारा लक्ष्य ट्यूरिंग मशीन TM का निर्माण करना है जो भाषा को स्वीकार करती है
एल=anbma(n+m) जहां n,m>=1
आइए उन शब्दों के उदाहरण लेते हैं जिन्हें TM स्वीकार कर सकता है,
- आबा, n=1,m=1
- आबा, n=2,m=1
- अब्बा, n=1,m=2
- आबा, n=3,m=1
वह है n गुना a उसके बाद m बार b उसके बाद n+m बार a फिर से। n,m>=1
कम से कम नहीं। a का हमेशा 3 होगा और b 1 होगा। जब दोनों n=m=1.
दृष्टिकोण का सारांश नीचे दिया गया है -
मशीन पहले सभी नं को स्वीकार करती है। a के बाद सभी m नं. बी के। फिर जैसे-जैसे अधिक मिलते हैं, यह पिछले इनपुट बी और ए को हटाना शुरू कर देता है। अंत में जब कोई नया नहीं आ रहा है और हेड पहले इनपुट कैरेक्टर तक पहुंचता है, तो इसका मतलब है कि सभी कैरेक्टर सही तरीके से प्रोसेस किए गए हैं। आइए इनपुट स्ट्रिंग के लिए चरण दर चरण अनुसरण करें -
राज्य q0 से संक्रमण
-
(क्यू0, ए) → (क्यू1, एक्स, आर)। राज्य q0 पर यदि वर्ण पढ़ा गया है तो राज्य q1 के लिए पारगमन है, इसे x बनाएं और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाईं ओर ले जाएं।
Ex − aabaaa → xabaaa (पहला अक्षर x हेड बन गया, सीधे अगले a पर चला गया)
-
(क्यू0, बी) → (क्यू3, एक्स, आर)। राज्य q0 पर यदि वर्ण पढ़ा गया है तो राज्य q3 के लिए पारगमन है, इसे x बनाएं और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाईं ओर ले जाएं।
Ex - बाबा…। → ज़ाबा…। (पहला कैरेक्टर x हेड बन गया, अगले a पर दाईं ओर ले जाया गया)
यहाँ x का उपयोग पहले वर्ण को दर्शाने के लिए किया जाता है।
राज्य q1 से संक्रमण
-
(क्यू1, ए) → (क्यू1, ए, आर)। राज्य q1 पर यदि वर्ण पढ़ा जाता है तो स्थिति q1 पर बने रहें, और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाएं जाएं।
उदा:xaabaaa… → xaabaaa… (आराम के लिए कुछ न करें और दाएं चलें)
-
(क्यू1, बी) → (क्यू2, बी, आर)। स्थिति q1 पर यदि पढ़ा गया वर्ण b है, तो स्थिति q1 पर बने रहें, और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाईं ओर जाएँ।
Ex − xaabaaa… → xaabaaa… (बाकी b के लिए कुछ न करें और दाएं चलें)
राज्य q2 से संक्रमण
-
(क्यू2, बी) → (क्यू2, बी, आर)। स्थिति q2 पर यदि पढ़ा गया वर्ण b है तो स्थिति q2 पर बने रहें, और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाईं ओर जाएँ।
Ex − xaabbbaaa… → xaabbbaaa… (बाकी के लिए b कुछ न करें और दाएं चलें)
-
(क्यू2, जेड) → (क्यू2, जेड, आर)। स्थिति q2 पर यदि पढ़ा गया वर्ण z है तो स्थिति q2 पर बने रहें, और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाईं ओर जाएँ।
Ex − xaabaazz… → xaabaazz… (आराम के लिए z कुछ भी न करें और दायें चलें)
-
(क्यू2, ए) → (क्यू3, जेड, एल)। स्थिति q2 पर यदि वर्ण पढ़ा गया a है, तो इसे z बनाएं, फिर स्थिति q3 में स्थानांतरित करें, और स्ट्रिंग में पिछले वर्ण को इंगित करने के लिए बाईं ओर जाएं।
Ex − xaabaazz… → xaabazzz… ( a को z से रिप्लेस करने और लेफ्ट मूव करने के लिए )
राज्य q3 से संक्रमण
-
(क्यू3, जेड) → (क्यू3, जेड, एल)। स्थिति q3 पर यदि पढ़ा गया वर्ण z है तो स्थिति q3 पर बने रहें, और स्ट्रिंग में पिछले वर्ण को इंगित करने के लिए बाईं ओर जाएँ।
Ex − xaabzzzz… → xaabzzzzz… (z के लिए कुछ न करें और बाईं ओर चलें)
-
(क्यू3, बी) → (क्यू2, जेड, आर)। स्थिति q2 पर यदि पढ़ा गया वर्ण b है तो इसे z बनाएं और Stateq2 पर पारगमन करें, और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाईं ओर जाएँ। सभी b को बदलें
Ex − xaabzzzz… → xaazzzzz… (b को z से रिप्लेस करने और दायीं ओर जाने के लिए)
-
(क्यू3, ए) → (क्यू2, जेड, आर)। राज्य q2 पर यदि वर्ण पढ़ा जाता है तो इसे z बनाएं और Stateq3 में स्थानांतरित करें, और अगले वर्ण को स्ट्रिंग में इंगित करने के लिए दाएं स्थानांतरित करें। सभी को बदलें
Ex − xaazzzz… → xaazzzzz… ( a को z से रिप्लेस करने के लिए और दायीं ओर मूव करने के लिए )
-
(क्यू3, एक्स) → (क्यू4, जेड, आर)। राज्य q2 पर यदि वर्ण पढ़ा गया x है तो इसे z बनाएं, फिर राज्य q3 में स्थानांतरित करें, और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाएं जाएं। पहला प्रतीक आ गया है।
Ex − xzzzzzzz… → zzzzzzzz… (x के लिए z से बदलें और दाएँ जाएँ)
राज्य q4 से संक्रमण
-
(क्यू4, जेड) → (क्यू4 जेड, आर)। अवस्था q4 पर यदि पढ़ा गया वर्ण z है तो स्थिति q4 पर बने रहें और स्ट्रिंग में अगले वर्ण को इंगित करने के लिए दाईं ओर जाएँ। सभी वर्ण अब z हैं।
Ex − zzzzzzzz… → zzzzzzzz… (सभी z के लिए कुछ न करें और दाएं चलें)
-
(क्यू4, $) → (क्यूएफ, $, आर)। स्थिति q4 पर यदि कोई वर्ण नहीं रहता है, तो अंत तक पहुँच जाता है। अंतिम स्थिति qf के लिए पारगमन। जिसका अर्थ है कि स्ट्रिंग स्वीकार की जाती है।
Ex − zzzzzzzz$ → zzzzzzzz (स्ट्रिंग के अंत के लिए, $ कुछ भी न करें और अंतिम स्थिति में आ जाएं)
आरेख ट्यूरिंग मशीन दिखाता है -
इनपुट
aabaaa q0: aabaaa → q1: xabaaa → q1: xabaaa → q2: xabaaa → q3: xabzaa → q2: xazzaa q2: xazzaa → q3: xazzza → q3: xazzza → q3: xazzza → q2: xzzzzza → q2: xzzzzza q2: xzzzzza → q2: xzzzzza → q2: xzzzzza → q2: xzzzzzz → q3: xzzzzzz…….. q3: xzzzzzz → q3: xzzzzzz → q4: zzzzzzz → q4: zzzzzzz…….q4: xzzzzzz$ → qf: xzzzzzz$
qf तक पहुंचने का मतलब है कि आबा स्वीकार कर लिया गया है