हमें एक भाषा "L" दी गई है और कार्य दिए गए भाषा के लिए एक पुशडाउन ऑटोमेटा बनाना है जो बताता है कि 0 की घटनाएं और 3 की घटनाएं बराबर होंगी और 1 की घटनाएं और 2 की घटनाएं बराबर होंगी और सभी संख्याओं की घटनाएं न्यूनतम 1 होनी चाहिए जो स्ट्रिंग को NULL भी बना सकती हैं और इसे ऑटोमेटा द्वारा स्वीकार किया जाना चाहिए।
पुशडाउन ऑटोमेटा क्या है?
एक पुशडाउन ऑटोमेटा या पुशडाउन ऑटोमेटन या PDA एक तकनीक है जिसका उपयोग संदर्भ-मुक्त व्याकरण को लागू करने के लिए किया जाता है, उसी तरह जैसे हम नियमित व्याकरण के लिए डिटरमिनिस्टिक फाइनाइट ऑटोमेटन या DFA डिज़ाइन करते हैं। एक DFA परिमित डेटा पर काम कर सकता है, लेकिन एक PDA अनंत डेटा पर काम कर सकता है। हम पुशडाउन ऑटोमेटा को "फाइनाइट स्टेट मशीन" और एक "स्टैक" के संयोजन के रूप में समझ सकते हैं।
एक पुशडाउन ऑटोमेटन के तीन घटक होते हैं:
एक इनपुट टेप,
एक कंट्रोल यूनिट, और
अनंत आकार का एक स्टैक।
एक PDA को औपचारिक रूप से 7-टपल (Q, Σ, S, δ, q0, I, F) के रूप में वर्णित किया जा सकता है:
Q अवस्थाओं की परिमित संख्या है
Σ इनपुट वर्णमाला है
S स्टैक प्रतीक हैं
δ संक्रमण फ़ंक्शन है: Q × (Σ ∪ {ε}) × S × Q × S*
q0 प्रारंभिक अवस्था है (q0 ∈ Q)
I प्रारंभिक स्टैक टॉप प्रतीक है (I ∈ S)
F स्वीकार करने वाली अवस्थाओं का समूह है (F ∈ Q)
आइए दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा बनाते हैं:
इस PDA द्वारा स्वीकार्य स्ट्रिंग्स निम्न रूप की हैं:
0n3n - 03, 0033, 000333 आदि। 0s की संख्या 3s की संख्या के बराबर है। जब m 0 है तो हमारे पास कोई 1s और 2s नहीं होंगे। 0s को पुश करते रहें और जैसे ही पहला 3 मिले तो 0s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुंचते हैं और कोई 0 नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।
1m2m - 12, 1122, 111222 आदि। 1s की संख्या 2s की संख्या के बराबर है। जब n 0 है तो हमारे पास कोई 0s और 3s नहीं होंगे। 1s को पुश करते रहें और जैसे ही पहला 2 मिले तो 1s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुंचते हैं और कोई 1 नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।
0n1m2m3n - 0123, 001233, 011223 आदि। 0s की संख्या 3s की संख्या के बराबर है और 1s 2s के बराबर हैं। 0s और 1s को पुश करते रहें। जैसे ही पहला 2 मिले तो अगर शीर्ष पर 1 है तो 1s पॉप करें और फिर शेष 3s के लिए 0s पॉप करें। यदि हम अंत तक पहुंचते हैं और कोई 0 नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।
NULL स्ट्रिंग भी स्वीकार की जाती है। 00102030।
आइए मशीन को समझते हैं
अवस्था 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.... बन जाता है। अगले 2 तक 1s को पुश करते रहें।
( 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/e ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 3 है तो 1 को पॉप करें और q3 पर रहें।
( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और q4 पर जाएं। NULL स्ट्रिंग के लिए।
अवस्था q5 के लिए संक्रमण:
( 1, 1/1,1 ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक भी 1 है तो 1 को स्टैक के शीर्ष पर पुश करें और q5 पर रहें। स्टैक 11.... बन जाता है। अगले 2 तक 1s को पुश करते रहें।
( 2, 1/e ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 को पॉप करें और q6 पर जाएं।
अवस्था q6 के लिए संक्रमण:
( 2, 1/e ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 को पॉप करें और q6 पर रहें।
( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और q4 पर जाएं। NULL स्ट्रिंग के लिए।
