पुशडाउन ऑटोमेटन, दो भाषाएं संभव हैं (या हालत)

Question

होमवर्क में हमें 2 भाषाओं के लिए एक पुशडाउन ऑटोमेटन का निर्माण करना था, लेकिन मेरी राय में ये दो अभ्यास हैं जिनके लिए ऑटोमेटन दोनों के लिए समान है।

जैसा कि मैं इसे समझता हूं, हम एक गैर-नियतात्मक पुशडाउन ऑटोमेटन का निर्माण कर सकते हैं, और हर बार जब हम चरित्र को पढ़ते हैं, तो हम ऑटोमेटन के 'विवेक' पर एक एकल ए या दो बार ए डाल सकते हैं।

इसके बाद, चरित्र b के लिए एक राज्य बनाया जाता है, जो हर बार जब वह A को पढ़ता है तो वह उसे स्टैक से बाहर निकाल देगा। इस तरह, ऑटोमेटन को पता है कि दोनों भाषाओं को कैसे संभालना है, जहां a की मात्रा b की मात्रा के बराबर है, और ऐसी भाषाएं भी हैं जहां b की मात्रा दोगुनी है।

क्या मैं सही हू? या क्या मैं कुछ न कुछ भूल रहा हूं?

यदि नहीं, तो मुझे यह समझना अच्छा लगेगा कि पहले अभ्यास में "या" स्थिति से कैसे निपटें।

धन्यवाद।

Answer 1

जबसे $L_2\ne L_3$, वे स्पष्ट रूप से एक ही pushdown automaton द्वारा स्वीकार नहीं किया जा सकता है। ऐसा लगता है कि आपके दिमाग में एक ऑटोमेटन है जो पहचानता है$L_3$। शायद पहचानने के लिए एक डिजाइन करने का सबसे आसान तरीका है$L_2$, दो नियतात्मक पुशडाउन ऑटोमेटा, एक के लिए डिजाइन करने के लिए है $\{a^nb^n:n\in\Bbb N\}$ और एक के लिए $\{a^{2n}b^n:n\in\Bbb N\}$। फिर उन्हें एक एकल पुशडाउन ऑटोमेटन में मिलाएं जिसमें संक्रमण है$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ तथा $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, कहाँ पे $q_0$ संयुक्त पीडीए की प्रारंभिक अवस्था है, $Z$ प्रारंभिक स्टैक प्रतीक है, और $q_1$ तथा $q_2$दो सहायक पुशडाउन ऑटोमेटा के प्रारंभिक राज्य हैं। दूसरे शब्दों में, पहली बात यह है कि संयुक्त पीडीए 'चुनता है' चाहे वह शब्द का एक प्रकार देखना हो$a^nb^n$ या एक प्रकार का शब्द $a^{2n}b^n$, और फिर यह उस विकल्प को निर्धारित करता है।