स्वीकृत भाषा और तय की गई भाषा
यदि कोई इनपुट स्ट्रिंग w के लिए अंतिम स्थिति में प्रवेश करता है तो एक TM एक भाषा को स्वीकार करता है। यदि ट्यूरिंग मशीन द्वारा स्वीकार किया जाता है, तो एक भाषा पुनरावर्ती रूप से टाइप करने योग्य (टाइप -0 व्याकरण से उत्पन्न) है।
एक टीएम एक भाषा का फैसला करता है अगर वह इसे स्वीकार करता है और भाषा में नहीं होने वाले किसी भी इनपुट के लिए अस्वीकार की स्थिति में प्रवेश करता है। यदि ट्यूरिंग मशीन द्वारा निर्णय लिया जाता है तो एक भाषा पुनरावर्ती है।
कुछ ऐसे मामले हो सकते हैं जहां एक टीएम बंद नहीं होता है। ऐसा टीएम भाषा को स्वीकार करता है, लेकिन यह इसे तय नहीं करता है।
ट्यूरिंग मशीन डिजाइन करना
ट्यूरिंग मशीन को डिजाइन करने के मूल दिशानिर्देशों को कुछ उदाहरणों की मदद से नीचे समझाया गया है।
उदाहरण 1
Α की विषम संख्या वाले सभी तारों को पहचानने के लिए एक TM डिज़ाइन करें।
Solution
ट्यूरिंग मशीन M निम्नलिखित चालों द्वारा निर्मित किया जा सकता है -
लश्कर q1 प्रारंभिक अवस्था हो।
अगर M में है q1; स्कैनिंग पर α, यह राज्य में प्रवेश करती हैq2 और लिखता है B (खाली)।
अगर M में है q2; स्कैनिंग पर α, यह राज्य में प्रवेश करती हैq1 और लिखता है B (खाली)।
उपरोक्त चाल से, हम यह देख सकते हैं M राज्य में प्रवेश करता है q1 अगर यह α की संख्या को स्कैन करता है, और यह राज्य में प्रवेश करता है q2यदि यह α की विषम संख्या को स्कैन करता है। इसलियेq2 केवल स्वीकार करने वाला राज्य है।
इसलिये,
एम = {{क्ष 1 , क्ष 2 }, {1}, {1, बी}, δ, क्ष 1 , बी, {क्ष 2 }}
by कहां दिया जाता है -
| टेप वर्णमाला प्रतीक | वर्तमान स्थिति 'q 1 ' | वर्तमान स्थिति 'q 2 ' |
|---|---|---|
| α | ब्रिक २ | ब्रिक १ |
उदाहरण 2
एक ट्यूरिंग मशीन डिज़ाइन करें जो एक बाइनरी नंबर का प्रतिनिधित्व करने वाले स्ट्रिंग को पढ़ता है और स्ट्रिंग में सभी प्रमुख 0 मिटा देता है। हालाँकि, यदि स्ट्रिंग में केवल 0 का समावेश है, तो यह एक 0 रखता है।
Solution
आइए मान लेते हैं कि इनपुट स्ट्रिंग को स्ट्रिंग के प्रत्येक सिरे पर एक खाली प्रतीक B, द्वारा समाप्त किया जाता है।
ट्यूरिंग मशीन, M, निम्नलिखित चालों द्वारा निर्मित किया जा सकता है -
लश्कर q0 प्रारंभिक अवस्था हो।
अगर M में है q0, 0 पढ़ने पर, यह सही चलता है, राज्य में प्रवेश करता है q1 और मिटा देता है। 1 पढ़ने पर, यह राज्य में प्रवेश करता है q2 और सही चलता है।
अगर M में है q1, 0 पढ़ने पर, यह सही चलता है और 0 मिटाता है, अर्थात, यह B के द्वारा 0 की जगह लेता है। सबसे बाईं ओर पहुँचने पर, यह प्रवेश करता हैq2और सही चलता है। यदि यह B तक पहुँच जाता है, अर्थात, स्ट्रिंग में केवल 0 का समावेश होता है, तो यह बाईं ओर चलती है और राज्य में प्रवेश करती हैq3।
अगर M में है q2, 0 या 1 पढ़ने पर, यह सही चलता है। बी तक पहुंचने पर, यह बाएं ओर बढ़ता है और राज्य में प्रवेश करता हैq4। यह पुष्टि करता है कि स्ट्रिंग में केवल 0 और 1 का समावेश है।
अगर M में है q3, यह B को 0 से बदल देता है, बाएं चलता है और अंतिम स्थिति में पहुंच जाता है qf।
अगर M में है q4, 0 या 1 पढ़ने पर, यह बाएँ चलता है। स्ट्रिंग की शुरुआत तक पहुंचने पर, यानी, जब यह बी को पढ़ता है, तो यह अंतिम स्थिति तक पहुंचता हैqf।
इसलिये,
M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}
by कहां दिया जाता है -
| टेप वर्णमाला प्रतीक | वर्तमान स्थिति 'q 0 ' | वर्तमान स्थिति 'q 1 ' | वर्तमान स्थिति 'q 2 ' | वर्तमान स्थिति 'q 3 ' | वर्तमान स्थिति 'q 4 ' |
|---|---|---|---|---|---|
| 0 | ब्रिक १ | ब्रिक १ | ओरक २ | - | ओलक ४ |
| 1 | १ रक २ | १ रक २ | १ रक २ | - | 1Lq 4 |
| ख | ब्रिक १ | बीलक ३ | ब्लक ४ | ओलक च | BRq एफ |