यहां हम देखेंगे कि भाषा L = {AiBjCk | i * j = k; i, j, k ≥ 1} के लिए ट्यूरिंग मशीन कैसे बनाएं। तो यह एक प्रकार की भाषा दर्शाता है जहां हम केवल तीन वर्ण A, B और C का उपयोग करेंगे। w एक स्ट्रिंग है। तो यदि w = AABBBBCCCCCCCC, तो ट्यूरिंग मशीन इसे स्वीकार करेगी।
इसे हल करने के लिए, हम इस दृष्टिकोण का उपयोग करेंगे।
पहले एक A को x से बदलें और दाएं जाएं। फिर सभी A को छोड़कर दाएं जाएं
जब हेड पहले B पर पहुंचे तो एक B को y से बदलें, फिर दाएं जाएं सभी मध्यवर्ती B को छोड़कर और प्रतिस्थापित B के अनुरूप अब एक C को z से बदलें और बाएं जाएं।
अब बाएं जाएं रास्ते में सभी z और B को छोड़कर।
जब पॉइंटर हाल के y पर पहुंचे, तो दाएं जाएं।
यदि पॉइंटर B पर इशारा कर रहा है तो चरण 2 से 4 दोहराएं, अन्यथा जब पॉइंटर z पर इशारा कर रहा हो तो बाएं जाएं सभी y को B में बदलते हुए और सभी A को छोड़ते हुए।
जब पॉइंटर सबसे हाल के x पर आए तो एक चरण दाएं जाएं।
यदि पॉइंटर अभी भी A पर इशारा कर रहा है तो उपरोक्त सभी चरण दोहराएं, अन्यथा जब हेड y पर हो तो दाएं जाएं सभी y और z को छोड़ते हुए।
जब $ पहुंच जाए तो बाएं जाएं। स्ट्रिंग स्वीकार की जाती है।
स्टेट ट्रांजिशन डायग्राम
