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