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