यहाँ हम देखेंगे कि L भाषा के लिए ट्यूरिंग मशीन कैसे बनाई जाती है ={AiBjCk | मैं * जे =के; मैं, जे, के 1}। तो यह एक प्रकार की भाषा का प्रतिनिधित्व करता है जहाँ हम केवल तीन वर्णों A, B और C का उपयोग करेंगे। w एक स्ट्रिंग है। तो अगर w =AABBBBCCCCCCCC, ट्यूरिंग मशीन इसे स्वीकार करेगी।
इसे हल करने के लिए, हम इस दृष्टिकोण का उपयोग करेंगे।
-
पहले A को x से बदलें और दाईं ओर चलें। फिर सभी ए को छोड़ दें और दाएं चलें
-
जब सिर पहले B तक पहुंच जाए तो एक B को y से बदल दें, फिर सभी मध्यवर्ती B को छोड़कर दाईं ओर जाएं और बदले गए B के अनुरूप अब एक C को z से बदलें और बाईं ओर जाएं।
-
अब रास्ते में सभी z और B को छोड़ते हुए बाईं ओर बढ़ें।
-
जब पॉइंटर हाल के y पर पहुँच जाए, तो दाएँ घूमें।
-
यदि पॉइंटर B की ओर इशारा कर रहा है तो चरण 2 से 4 दोहराएँ, अन्यथा जब पॉइंटर z की ओर इशारा कर रहा हो तो सभी y को B से बदलकर और सभी A को छोड़ते हुए बाईं ओर जाएँ।
-
जब पॉइंटर सबसे हाल के x पर आता है तो दाएं कदम पर जाता है।
-
यदि सूचक अभी भी A की ओर इशारा कर रहा है तो उपरोक्त सभी चरणों को दोहराएं, अन्यथा जब सिर y पर हो तो सभी y और z को छोड़ते हुए दाईं ओर बढ़ें।
-
जब $ पहुंच जाए तो बाएं घूमें। स्ट्रिंग स्वीकार की जाती है।
राज्य संक्रमण आरेख
