पुशडाउन ऑटोमेटा स्वीकृति

पीडीए स्वीकार्यता को परिभाषित करने के दो अलग-अलग तरीके हैं।

अंतिम राज्य की स्वीकार्यता

अंतिम राज्य की स्वीकार्यता में, एक पीडीए एक स्ट्रिंग को स्वीकार करता है, जब पूरे स्ट्रिंग को पढ़ने के बाद, पीडीए एक अंतिम स्थिति में है। प्रारंभिक अवस्था से, हम ऐसी चालें बना सकते हैं जो किसी भी स्टैक मान के साथ अंतिम स्थिति में समाप्त होती हैं। जब तक हम अंतिम स्थिति में होते हैं तब तक ढेर के मूल्य अप्रासंगिक होते हैं।

एक पीडीए (Q, S, S, q, q 0 , I, F) के लिए, अंतिम राज्यों F के सेट द्वारा स्वीकृत भाषा है -

एल (पीडीए) = {w | (q 0 , w, I) (* (q,,, x), q} F}

किसी भी इनपुट स्टैक स्ट्रिंग के लिए x

खाली स्टैक स्वीकार्यता

यहां एक पीडीए एक स्ट्रिंग को स्वीकार करता है, जब पूरे स्ट्रिंग को पढ़ने के बाद, पीडीए ने अपने स्टैक को खाली कर दिया है।

एक पीडीए (Q, ∑, S, q, q 0 , I, F) के लिए, खाली स्टैक द्वारा स्वीकार की गई भाषा -

एल (पीडीए) = {w | (q 0 , w, I) (* (q, ε,,), q} Q}

उदाहरण

एक पीडीए का निर्माण करता है जो स्वीकार करता है L = {0n 1n | n ≥ 0}

समाधान

यह भाषा L = {ε, 01, 0011, 000111, …………………………} स्वीकार करती है।

यहाँ, इस उदाहरण में, की संख्या ‘a’ तथा ‘b’ एक ही होना है।

  • प्रारंभ में हमने एक विशेष प्रतीक रखा ‘$’ खाली ढेर में।

  • फिर राज्य में q2, अगर हमारे पास इनपुट 0 है और शीर्ष अशक्त है, तो हम 0 को स्टैक में धकेल देते हैं। यह पुनरावृति हो सकती है। और अगर हम 1 इनपुट का सामना करते हैं और शीर्ष 0 है, तो हम इस 0 को पॉप करते हैं।

  • फिर राज्य में q3, अगर हम 1 इनपुट का सामना करते हैं और शीर्ष 0 है, तो हम इसे 0. पॉप करते हैं। यह भी पुनरावृति हो सकता है। और अगर हम 1 इनपुट का सामना करते हैं और शीर्ष 0 है, तो हम शीर्ष तत्व को पॉप करते हैं।

  • यदि स्टैक के शीर्ष पर विशेष प्रतीक '$' अंकित है, तो यह पॉप आउट हो जाता है और अंत में यह स्वीकार करने की स्थिति में जाता है q 4

उदाहरण

एक पीडीए है कि एल स्वीकार करता है का निर्माण = {ww आर | w = (a + b) *}

Solution

प्रारंभ में हम खाली स्टैक में एक विशेष प्रतीक '$' डालते हैं। राज्य मेंq2, को wपढ़ा जा रहा है। राज्य मेंq3प्रत्येक 0 या 1 को पॉप अप किया जाता है जब वह इनपुट से मेल खाता है। यदि कोई अन्य इनपुट दिया जाता है, तो पीडीए मृत अवस्था में चला जाएगा। जब हम उस विशेष प्रतीक '$' पर पहुँचते हैं, तो हम स्वीकार करने की स्थिति में जाते हैंq4