एक डीएफए के आरेख होने के बाद, मैं इसे ट्यूरिंग मशीन में कैसे परिवर्तित कर सकता हूं? क्या मुझे उस भाषा को ढूंढना है जिसे डीएफए स्वीकार करता है और फिर ट्यूरिंग मशीन बनाता है? या क्या कोई सीधा तरीका है?एक डीएफए को ट्यूरिंग मशीन में कैसे परिवर्तित करें?
धन्यवाद।
डीएफए में प्रत्येक संक्रमण इनपुट के एक चरित्र को पढ़ता है, एक संक्रमण के बाद, फिर इनपुट के अगले चरित्र पर जाता है। एक बार सभी इनपुट पढ़े जाने के बाद, डीएफए स्वीकार करता है कि यह स्वीकार्य स्थिति में है और अन्यथा अस्वीकार करता है।
आप सीधे इसे ट्यूरिंग मशीन के साथ अनुकरण कर सकते हैं। डीएफए में प्रत्येक राज्य के लिए एक राज्य बनाकर ट्यूरिंग मशीन के परिमित राज्य नियंत्रण का निर्माण करें। चरित्र सी पर डीएफए में प्रत्येक संक्रमण के लिए, टीएम में उस संक्रमण को प्रतिस्थापित करें, चरित्र सी पढ़ने पर, टेप में कुछ मनमाने ढंग से चरित्र लिखता है (इससे कोई फर्क नहीं पड़ता) और फिर टेप हेड दाएं स्थानांतरित कर रहा है (टेप पर अगले स्थान पर)। फिर, प्रत्येक राज्य के लिए, उस राज्य से रिक्त प्रतीक पर या तो टीएम की स्वीकृति स्थिति या टीएम की अस्वीकार स्थिति (उस राज्य के आधार पर स्वीकार या अस्वीकार कर रहा है) पर एक संक्रमण शुरू करें। यह टीएम इनपुट स्ट्रिंग में मैन्युअल रूप से कदम उठाकर डीएफए को प्रभावी ढंग से चलाता है और आखिरकार यह तय करता है कि रन के अंत में स्वीकार या अस्वीकार करना है या नहीं।
आशा है कि इससे मदद मिलती है!
जब कोई चरित्र सी पढ़ा जाता है तो ऐसा होता है जिसके परिणामस्वरूप राज्य संक्रमण नहीं होता है? क्या एक मनमाना चरित्र लिखा गया है और टेप हेड अभी भी चलता है? – Paradox
@ पैराडाक्स डीएफए की अधिकांश परिभाषाओं के तहत, डीएफए में प्रत्येक चरित्र और प्रत्येक राज्य के लिए एक संक्रमण परिभाषित होना चाहिए। इसी तरह, अधिकांश टीएम को इस तरह से परिभाषित किया जाता है जो आपको प्रतिबंधित करता है कि इनपुट के रूप में किस प्रकार के प्रतीकों को खिलाया जा सकता है, और इसलिए आपको इसके बारे में चिंता करने की आवश्यकता नहीं होगी: किसी भी टीएम प्रतीक का सामना करना पड़ सकता है जो डीएफए के पास होगा संक्रमण के लिए परिभाषित किया गया। वैकल्पिक रूप से, यदि आपके पास वह प्रतिबंध नहीं है, तो बस अस्वीकार करें - डीएफए की भाषा केवल वर्णमाला से वर्णों का उपयोग करने के लिए प्रतिबंधित है, इसलिए यदि आप एक विदेशी चरित्र देखते हैं, तो आप जानते हैं कि स्ट्रिंग भाषा में नहीं है। – templatetypedef