यहाँ हम देखेंगे कि L ={WW |W {0, 1}} से संबंधित भाषा के लिए ट्यूरिंग मशीन कैसे बनाई जाती है। तो यह एक प्रकार की भाषा का प्रतिनिधित्व करता है जहाँ हम केवल दो वर्णों 0s और 1s का उपयोग करेंगे। डब्ल्यू एक स्ट्रिंग है। तो अगर w =10110, तो ट्यूरिंग मशीन स्ट्रिंग z =1011010110 को स्वीकार करेगी।
इसे हल करने के लिए, हम इस दृष्टिकोण का उपयोग करेंगे। पहली बात यह है कि स्ट्रिंग के मध्य बिंदु को खोजने के लिए, हम 0 को x और 1 को y में बदल देंगे। इसे लगातार करने के बाद एक बिंदु पर पहुंच जाता है जब सभी 0 और 1 को क्रमशः x और x में बदल दिया जाता है। अब, हम स्ट्रिंग के मध्य बिंदु पर हैं। तो, हमारा पहला उद्देश्य पूरा हुआ।
अब, मध्य बिंदु के बाईं ओर सभी x और y को 0 और 1 में परिवर्तित करें। अब पहला आधा स्ट्रिंग 0 और 1 के रूप में है। स्ट्रिंग का दूसरा भाग x और y के रूप में है।
अब, फिर से स्ट्रिंग की शुरुआत से शुरू करें। यदि आपके पास 0 है तो इसे x में परिवर्तित करें और दूसरी छमाही तक पहुंचने तक दाएं आगे बढ़ें, यहां यदि हम x पाते हैं तो इसे रिक्त (बी) में परिवर्तित करें। फिर x या x ज्ञात करने तक पीछे की ओर जाएं। हम इसके दाईं ओर 0 या 1 को क्रमशः x या y में परिवर्तित करते हैं और संगत रूप से, इसके x या y को स्ट्रिंग के दूसरे भाग में रिक्त (B) में परिवर्तित करते हैं।
ऐसा तब तक करते रहें जब तक कि स्ट्रिंग के बाएं हिस्से के सभी प्रतीकों को x और y में और स्ट्रिंग के दाईं ओर के सभी प्रतीकों को रिक्त स्थान में परिवर्तित न कर दें। जब एक भाग पूरी तरह से परिवर्तित हो जाता है लेकिन फिर भी दूसरे आधे हिस्से में कुछ प्रतीकों को अपरिवर्तित छोड़ दिया जाता है तो स्ट्रिंग स्वीकार नहीं की जाएगी। अगर हमें दूसरी छमाही में क्रमशः 0 या 1 के लिए पहली छमाही में x या y नहीं मिला। फिर भी स्ट्रिंग स्वीकार नहीं की जाएगी।
राज्य संक्रमण आरेख
