L ={0(n+m)1m2n | . के लिए पुशडाउन ऑटोमेटा का निर्माण करें एम, एन =0} सी++ में

हमें "L" भाषा दी गई है और कार्य दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा का निर्माण करना है जो बताता है कि 0 की घटनाएं 1 और 2 की घटनाओं का जोड़ होंगी और साथ ही, 1 और 2 की घटना न्यूनतम होगी जो स्ट्रिंग को NULL भी बना सकती है और इसे ऑटोमेटा द्वारा स्वीकार किया जाना चाहिए।

पुशडाउन ऑटोमेटा क्या है?

एक पुशडाउन ऑटोमेटा या पुशडाउन ऑटोमेटन या पीडीए एक संदर्भ-मुक्त व्याकरण को लागू करने की एक तकनीक है जिस तरह से हम एक नियमित व्याकरण के लिए नियतात्मक परिमित ऑटोमेटन या डीएफए डिजाइन करते हैं। एक डीएफए परिमित डेटा पर काम कर सकता है, लेकिन एक पीडीए अनंत डेटा पर काम कर सकता है। हम पुशडाउन ऑटोमेटा को "परिमित स्टेटमशीन" और "स्टैक" के संयोजन के रूप में समझ सकते हैं।

एक पुशडाउन ऑटोमेटन में तीन घटक होते हैं -

• एक इनपुट टेप,

• एक नियंत्रण इकाई, और

• अनंत आकार वाला ढेर।

एक PDA को औपचारिक रूप से 7−tuple (Q, Ʃ, S, , q0, I, F) -

• Q राज्यों की परिमित संख्या है

• Ʃ इनपुट वर्णमाला है

• S स्टैक सिंबल है

• δ संक्रमण फलन है:Q × (Ʃ {ε}) × S × Q × S*

• q0 प्रारंभिक अवस्था है (q0 Q)

• I प्रारंभिक स्टैक शीर्ष प्रतीक है (I ε S)

• F, स्वीकार करने वाली अवस्थाओं का एक समूह है (F ε Q)

आइए दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा बनाएं -

इस पीडीए द्वारा स्वीकार्य स्ट्रिंग्स फॉर्म के हैं -

• 1. 0 ⁿ 2 ⁿ :02, 0022, 000222 आदि। 0 की संख्या संख्या के बराबर है। 2s का। जब m 0 होता है तो हमारे पास 1s नहीं होता है। 0s को पुश करते रहें और जैसे ही पहला 2 सामने आए तो 0s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और 0s के साथ छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।

• 0 ^m 1 ^m :01, 0011, 000111 आदि। 0 की संख्या संख्या के बराबर है। 1s का। जब n 0 है तो हमारे पास कोई 2s नहीं होगा। 0s को पुश करते रहें और जैसे ही पहला 1 सामने आए तो 0s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और 0s के साथ छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।

• 0 ^n+m 1 ^m 2 ⁿ :0012, 000112, 000122 आदि। 0 की संख्या संख्या के योग के बराबर है। 1s और 2s का। 0s को पुश करते रहें और जैसा कि पहले 1 का सामना करना पड़ता है, फिर उन 0s को तब तक पॉप करें जब तक कोई 1s न बचे। फिर 0s को फिर से पुश करते रहें और जैसा कि पहले 2 का सामना करना पड़ता है, तो उन 0s को तब तक पॉप करें जब तक कि कोई 2s न बचे। स्ट्रिंग स्वीकार की जाएगी।

• NULL स्ट्रिंग भी स्वीकार की जाती है। 0 ⁰ 1 ⁰ 2 ⁰

आइए मशीन को समझते हैं

• राज्य q0 के लिए संक्रमण:

  • 0, I/0I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक 0 है तो 0 को स्टैक के शीर्ष पर धकेलें और q0 पर बने रहें। स्टैक 0I बन जाता है...

  • ( 0, 0/00 ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक भी 0 है तो 0 को स्टैक के शीर्ष पर धकेलें और q0 पर बने रहें। स्टैक 00 हो जाता है.... अगले 1 या 2 तक 0s को पुश करते रहें।

  • ( 1, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 1 है तो 0 पॉप करें और q1 पर जाएं।

  • ( 2, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 2 है तो 0 पॉप करें और q2 पर जाएं।

  • ( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और qf पर जाएं। NULL स्ट्रिंग के लिए।

• राज्य q1 के लिए संक्रमण -

  • ( 1, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 1 है तो 0 पर पॉप करें और q1 पर बने रहें।

  • ( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और qf पर जाएं।

  • ( 2, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 2 है तो 0 पॉप करें और q2 पर जाएं।

• राज्य q2 के लिए संक्रमण -

  • ( 2, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 2 है तो 0 पॉप करें और q2 पर बने रहें।

  • ($, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और qf पर जाएं।