ट्यूरिंग मशीन: एक ट्यूरिंग मशीन टाइप 0 व्याकरण द्वारा उत्पन्न भाषा के शब्दों को स्वीकार करने के लिए उपयोग किया जाने वाला उपकरण है। एक ट्यूरिंग मशीन (TM) एक गणितीय मॉडल है जिसमें अनंत लंबाई का एक टेप होता है जिसे सेल में विभाजित किया जाता है जिस पर इनपुट दिया जाता है। इसमें एक हेड होता है जो इनपुट टेप को पढ़ता है। एक स्टेट रजिस्टर ट्यूरिंग मशीन की अवस्था को संग्रहीत करता है। एक इनपुट सिंबल पढ़ने के बाद, इसे दूसरे सिंबल से बदल दिया जाता है, इसकी आंतरिक अवस्था बदल जाती है, और यह एक सेल को दाएं या बाएं ले जाता है। यदि TM अंतिम अवस्था तक पहुंच जाता है, तो इनपुट स्ट्रिंग स्वीकार कर ली जाती है, अन्यथा अस्वीकार कर दी जाती है।
एक TM को औपचारिक रूप से 7-टपल (Q, X, Σ, δ, q0, B, F) के रूप में वर्णित किया जा सकता है जहां:
- Q अवस्थाओं का एक परिमित समुच्चय है
- X टेप वर्णमाला है
- Σ इनपुट वर्णमाला है
- δ एक संक्रमण फ़ंक्शन है; δ: Q × X → Q × X × {लेफ्ट_शिफ्ट, राइट_शिफ्ट}।
- q0 प्रारंभिक अवस्था है
- B ब्लैंक सिंबल है
- F अंतिम अवस्थाओं का समुच्चय है
हमारा लक्ष्य एक ट्यूरिंग मशीन TM का निर्माण करना है जो भाषा को स्वीकार करती है
L = an bm a(n+m) जहां n,m ≥ 1
उन शब्दों के उदाहरण लें जिन्हें TM स्वीकार कर सकता है,
- abaa, n=1,m=1
- aabaaa, n=2,m=1
- abbaaa, n=1,m=2
- aaabaaaa, n=3,m=1
यानी n बार a फिर m बार b फिर n+m बार a फिर से। n,m ≥ 1
a की न्यूनतम संख्या हमेशा 3 होगी और b की 1। जब n=m=1 दोनों हों।
दृष्टिकोण नीचे संक्षेपित है:
मशीन पहले n संख्या के a और फिर m संख्या के b को स्वीकार करती है। फिर जैसे-जैसे अधिक a आते हैं, यह पिछले इनपुट b और a को हटाना शुरू कर देती है। अंत में जब कोई नया a नहीं आ रहा होता और हेड पहले इनपुट कैरेक्टर तक पहुंच जाता है, तो इसका मतलब है कि सभी कैरेक्टर सही ढंग से प्रोसेस हो गए हैं। आइए इनपुट स्ट्रिंग के लिए चरण-दर-चरण अनुसरण करें:
स्टेट q0 से संक्रमण:
- δ(q0, a) → (q1, x, R)। स्टेट q0 पर यदि पढ़ा गया कैरेक्टर a है तो स्टेट q1 पर जाएं, इसे x बनाएं और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं।
- δ(q0, b) → (q3, x, R)। स्टेट q0 पर यदि पढ़ा गया कैरेक्टर b है तो स्टेट q3 पर जाएं, इसे x बनाएं और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं।
यहां x पहले कैरेक्टर को दर्शाने के लिए उपयोग किया जाता है।
स्टेट q1 से संक्रमण:
- δ(q1, a) → (q1, a, R)। स्टेट q1 पर यदि पढ़ा गया कैरेक्टर a है तो q1 पर रहें, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं।
- δ(q1, b) → (q2, b, R)। स्टेट q1 पर यदि पढ़ा गया कैरेक्टर b है तो q1 पर रहें, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं।
स्टेट q2 से संक्रमण:
- δ(q2, b) → (q2, b, R)। स्टेट q2 पर यदि पढ़ा गया कैरेक्टर b है तो q2 पर रहें, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं।
- δ(q2, z) → (q2, z, R)। स्टेट q2 पर यदि पढ़ा गया कैरेक्टर z है तो q2 पर रहें, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं।
- δ(q2, a) → (q3, z, L)। स्टेट q2 पर यदि पढ़ा गया कैरेक्टर a है, तो इसे z बनाएं फिर स्टेट q3 पर जाएं, और स्ट्रिंग में पिछले कैरेक्टर को इंगित करने के लिए बाएं जाएं।
स्टेट q3 से संक्रमण:
- δ(q3, z) → (q3, z, L)। स्टेट q3 पर यदि पढ़ा गया कैरेक्टर z है तो q3 पर रहें, और स्ट्रिंग में पिछले कैरेक्टर को इंगित करने के लिए बाएं जाएं।
- δ(q3, b) → (q2, z, R)। स्टेट q2 पर यदि पढ़ा गया कैरेक्टर b है तो इसे z बनाएं और स्टेट q2 पर जाएं, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं। सभी b को प्रतिस्थापित करें।
- δ(q3, a) → (q2, z, R)। स्टेट q2 पर यदि पढ़ा गया कैरेक्टर a है तो इसे z बनाएं और स्टेट q3 पर जाएं, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं। सभी a को प्रतिस्थापित करें।
- δ(q3, x) → (q4, z, R)। स्टेट q2 पर यदि पढ़ा गया कैरेक्टर x है तो इसे z बनाएं फिर स्टेट q3 पर जाएं, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं। पहला सिंबल पहुंच गया है।
स्टेट q4 से संक्रमण:
- δ(q4, z) → (q4, z, R)। स्टेट q4 पर यदि पढ़ा गया कैरेक्टर z है तो q4 पर रहें, और स्ट्रिंग में अगले कैरेक्टर को इंगित करने के लिए दाएं जाएं। सभी कैरेक्टर अब z हैं।
- δ(q4, $) → (qf, $, R)। स्टेट q4 पर यदि कोई कैरेक्टर नहीं बचा, अंत पहुंच गया। अंतिम स्टेट qf पर जाएं। जिसका मतलब है स्ट्रिंग स्वीकार कर ली गई।
आरेख ट्यूरिंग मशीन दिखाता है:
इनपुट
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 पर पहुंचा मतलब aabaaa स्वीकार कर लिया गया
