हमें एक भाषा "L" दी गई है और कार्य दिए गए भाषा के लिए एक पुशडाउन ऑटोमेटा बनाना है जो बताता है कि 1 की घटनाएं 0 की घटनाओं और 2 की घटनाओं के योग के बराबर होंगी और साथ ही, 0 और 2 की घटनाएं न्यूनतम एक होंगी जो स्ट्रिंग को 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 द्वारा स्वीकार्य स्ट्रिंग्स निम्न रूप की हैं:
0m1m - 01, 0011, 000111 आदि। 0s की संख्या 1s की संख्या के बराबर है। जब n 0 है तो हमारे पास कोई 2s नहीं होंगे। 0s को पुश करते रहें और जैसे ही पहला 1 मिले तो 0s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुंचते हैं और कोई 0 नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।
1n2n - 12, 1122, 111222 आदि। 1s की संख्या 2s की संख्या के बराबर है। जब m 0 है तो हमारे पास कोई 0s नहीं होंगे। 1s को पुश करते रहें और जैसे ही पहला 2 मिले तो 1s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुंचते हैं और कोई 1 नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।
0n1m+n2m - 0112, 001112, 001112 आदि। 1s की संख्या 0s और 2s की संख्या के योग के बराबर है। 0s को पुश करते रहें जैसे ही पहला 1 मिले तो 0s को तब तक पॉप करें जब तक कोई 0 न बचे। अब फिर से 1s को पुश करें जब तक पहला 2 न मिले। फिर प्रत्येक 2 के लिए 1s को पॉप करना शुरू करें जब तक हम बिना 1s के न रह जाएं। यदि हम अंत तक पहुंचते हैं और कोई 1 नहीं बचता तो स्ट्रिंग स्वीकार की जाती है।
NULL स्ट्रिंग भी स्वीकार की जाती है। 001020
आइए मशीन को समझते हैं
अवस्था q0 के लिए संक्रमण:
( 0, I/0I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक 0 है तो 0 को स्टैक के शीर्ष पर पुश करें और q0 पर रहें। स्टैक 0I... बन जाता है।
( 0, 0/00 ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक भी 0 है तो 0 को स्टैक के शीर्ष पर पुश करें और q0 पर रहें। स्टैक 00.... बन जाता है। अगले 1 या 2 तक 0s को पुश करते रहें।
( 1, I/1I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक 1 है तो 1 को स्टैक के शीर्ष पर पुश करें और q1 पर जाएं। स्टैक 1I... बन जाता है।
( 1, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 1 है तो 0 को पॉप करें और q1 पर जाएं।
( 1, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 1 है तो 0 को पॉप करें और q1 पर जाएं।
अवस्था q1 के लिए संक्रमण:
( 1, 1/11 ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक भी 1 है तो 1 को स्टैक के शीर्ष पर पुश करें और q1 पर रहें। स्टैक 11.... बन जाता है। अगले 0 या 2 तक 1s को पुश करते रहें।
( 1, 0/$ ) - यदि स्टैक का शीर्ष 0 है और वर्तमान इनपुट प्रतीक 1 है तो 0 को पॉप करें और q1 पर रहें।
( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और qf पर जाएं।
( 2, 1/$ ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 को पॉप करें और q2 पर जाएं।
अवस्था q2 के लिए संक्रमण:
( 2, 1/$ ) - यदि स्टैक का शीर्ष 1 है और वर्तमान इनपुट प्रतीक 2 है तो 1 को पॉप करें और q2 पर रहें।
( $, I/I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और qf पर जाएं।
