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

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

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

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

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

एक इनपुट टेप,
एक नियंत्रण इकाई, और
अनंत आकार वाला ढेर।

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

के रूप में वर्णित किया जा सकता है।

Q राज्यों की परिमित संख्या है
Σ इनपुट वर्णमाला है
S स्टैक सिंबल है
δ संक्रमण फलन है:Q × (Σ {ε}) × S × Q × S*
q0 प्रारंभिक अवस्था है (q0 Q)
I प्रारंभिक स्टैक शीर्ष प्रतीक है (I Ε S)
F, स्वीकार करने वाली अवस्थाओं का एक समूह है (F Ε Q)

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

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

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

0ⁿ 3ⁿ - 03, 0033, 000333 आदि। 0 की संख्या संख्या के बराबर है। 3s का। जब m 0 होता है तो हमारे पास 1s और 2s नहीं होंगे। 0s को पुश करते रहें और जैसे ही पहला 3 सामने आए तो 0s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और 0s के साथ छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।
1^m 2^m -12, 1122, 111222 आदि। 1s की संख्या संख्या के बराबर है। 2s का। जब n 0 होता है तो हमारे पास 0 और 3s नहीं होते हैं। 1s को पुश करते रहें और जैसे ही पहला 2 सामने आए फिर 1s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और 1s के साथ छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।
0ⁿ 1^m 2^m 3ⁿ - 0123, 001233, 011223 आदि। 0 की संख्या संख्या के बराबर है। 3s और 1s 2s के बराबर। 0s और 1s को आगे बढ़ाते रहें। जैसे ही पहले 2 का सामना करना पड़ता है, तो 1s पॉप करें यदि यह शीर्ष पर है और फिर शेष 3s के लिए 0s पॉप करें। अगर हम अंत तक पहुँच जाते हैं और कोई 0 नहीं बचा है तो स्ट्रिंग स्वीकार कर ली जाती है।
NULL स्ट्रिंग भी स्वीकार की जाती है। 0⁰ 1⁰ 2⁰ 3⁰ ।

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

राज्य q0 के लिए संक्रमण -
- ( 0, I/0,I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक 0 है तो 0 को स्टैक के शीर्ष पर धकेलें और q0 पर बने रहें। स्टैक 0I बन जाता है...
- ( 0, 0/0,0) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक भी 0 है तो 0 को स्टैक के शीर्ष पर धकेलें और q0 पर बने रहें। स्टैक 00 हो जाता है.... अगले 1 या 3 तक 0s को पुश करते रहें।
- ( 1, 0/1,0 ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 1 है तो स्टैक के शीर्ष पर 1 को धक्का दें और q1 पर जाएं। स्टैक 10 हो जाता है...
- ( 1, I/1,I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक 1 है तो 1 पुश करें और q5 पर जाएं।
- ( 3, 0/e ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 3 है तो 0 पॉप करें और q3 पर जाएं।
- ( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और q4 पर जाएं। NULL स्ट्रिंग के लिए।
राज्य q1 के लिए संक्रमण -
- ( 1, 1/11 ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक भी 1 है तो स्टैक के शीर्ष पर 1 पुश करें और q1 पर बने रहें। स्टैक 11 हो जाता है.... 1s को अगले 2 तक दबाते रहें।
- ( 2, 1/e ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 पॉप करें और q2 पर जाएं।
राज्य q2 के लिए संक्रमण -
- ( 2, 1/e ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 पॉप करें और q2 पर बने रहें।
- ( 3, 0/e ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 3 है तो 0 पॉप करें और q3 पर जाएं।
राज्य q3 के लिए संक्रमण -
- ( 3, 0/ई ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 3 है तो पॉप 1 और q3 पर बने रहें।
- ( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और q4 पर जाएं। NULL स्ट्रिंग के लिए।
राज्य q5 के लिए संक्रमण -
- ( 1, 1/1,1) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक भी 1 है, तो स्टैक के शीर्ष पर 1 पुश करें और q5 पर बने रहें। स्टैक 11 हो जाता है.... 1s को अगले 2 तक दबाते रहें।
- ( 2, 1/e ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 पॉप करें और q6 पर जाएं।
राज्य q6 के लिए संक्रमण -
- ( 2, 1/e ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 पॉप करें और q6 पर बने रहें।
- ( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और q4 पर जाएं। NULL स्ट्रिंग के लिए।