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