यहां हम देखेंगे कि भाषा L = {0n1n2n | n ≥ n} के लिए ट्यूरिंग मशीन कैसे बनाएं। तो यह एक प्रकार की भाषा दर्शाता है जहां हम केवल तीन वर्ण 0, 1 और 2 का उपयोग करेंगे। w एक स्ट्रिंग है। तो यदि w = 000111222, तो ट्यूरिंग मशीन इसे स्वीकार करेगी।
इसे हल करने के लिए, हम इस दृष्टिकोण का उपयोग करेंगे। पहले सामने से एक 0 को x से बदलें, फिर दाएं जाते रहें जब तक हमें एक 1 न मिल जाए और इस 1 को y से बदलें। फिर से, दाएं जाते रहें जब तक हमें एक 2 न मिल जाए, इसे z से बदलें और बाएं जाएं। अब बाएं जाते रहें जब तक हमें एक x न मिल जाए। जब हमें यह मिल जाए, तो एक दाएं जाएं, फिर ऊपर बताई गई वही प्रक्रिया का पालन करें।
एक स्थिति आती है जब हमें एक x तुरंत एक y के बाद मिलता है। इस बिंदु पर हम दाएं जाते रहते हैं और जांचते रहते हैं कि सभी 1 और 2 को y और z में बदल दिया गया है या नहीं। यदि नहीं, तो स्ट्रिंग स्वीकार नहीं की जाती। यदि हम $ तक पहुंच जाते हैं तो स्ट्रिंग स्वीकार की जाती है।
स्टेट ट्रांजिशन डायग्राम
