कैसे एक निर्माण करने के लिए pushdown ऑटोमेटा के लिए एल= { w ∈ {a, b}* | डब्ल्यू के बराबर नहीं xx^R के लिए कुछ x ∈ {a, b}* }
0
मैं मान रहा हूँ आप चाहते हैं कि एक गैर नियतात्मक धक्का-नीचे automaton. मुझे नहीं लगता कि यह संभव है के साथ एक नियतात्मक पीडीए.
इस तरह लगता है एक होमवर्क समस्या है, तो मैं जा रहा हूँ करने के लिए एक सामान्य रूपरेखा दे:
आप अनिवार्य रूप से लगता है, जहां के केंद्र स्ट्रिंग है. आप धक्का तत्वों पर हो चुकी है, जब तक कुछ बिंदु पर आपको लगता है कि आप पहुँच चुके हैं के केंद्र स्ट्रिंग. आप फिर से शुरू की तुलना करने के लिए अपने इनपुट तत्वों है कि आप कर रहे हैं popping बंद हो चुकी है । आप असफल हो, यदि वे मेल नहीं खाते. आप सफल हो, तो आप अंत तक पहुँचने के लिए इनपुट के रूप में वास्तव में ढेर खाली है ।