हमें "L" भाषा दी गई है और कार्य दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा का निर्माण करना है जो बताता है कि 1 की घटनाएँ 0 और 2 की घटनाओं का जोड़ होंगी और साथ ही, 0 और 2 की घटना न्यूनतम होगी जो स्ट्रिंग को NULL भी बना सकती है और इसे ऑटोमेटा द्वारा स्वीकार किया जाना चाहिए।
पुशडाउन ऑटोमेटा क्या है?
एक पुशडाउन ऑटोमेटा या पुशडाउन ऑटोमेटन या पीडीए एक संदर्भ-मुक्त व्याकरण को लागू करने की एक तकनीक है जिस तरह से हम एक नियमित व्याकरण के लिए नियतात्मक परिमित ऑटोमेटन या डीएफए डिजाइन करते हैं। एक डीएफए परिमित डेटा पर काम कर सकता है, लेकिन एक पीडीए अनंत डेटा पर काम कर सकता है। हम पुशडाउन ऑटोमेटा को "परिमित स्टेटमशीन" और "स्टैक" के संयोजन के रूप में समझ सकते हैं।
एक पुशडाउन ऑटोमेटन में तीन घटक होते हैं -
-
एक इनपुट टेप,
-
एक नियंत्रण इकाई, और
-
अनंत आकार वाला एक ढेर।
एक पीडीए को औपचारिक रूप से 7-टुपल (क्यू, Σ, एस, , क्यू 0, आई, एफ) के रूप में वर्णित किया जा सकता है -
-
Q राज्यों की परिमित संख्या है
-
Σ इनपुट वर्णमाला है
-
S स्टैक सिंबल है
-
δ संक्रमण फलन है:Q × (Σ {ε}) × S × Q × S*
-
q0 प्रारंभिक अवस्था है (q0 Q)
-
I प्रारंभिक स्टैक शीर्ष प्रतीक है (I Ε S)
-
F, स्वीकार करने वाली अवस्थाओं का एक समूह है (F Ε Q)
आइए दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा बनाएं -
इस पीडीए द्वारा स्वीकार्य स्ट्रिंग्स फॉर्म के हैं -
-
0 m 1 m - 01, 0011, 000111 आदि। 0 की संख्या संख्या के बराबर है। 1s का। जब n 0 है तो हमारे पास कोई 2s नहीं होगा। 0s को पुश करते रहें और जैसे ही पहला 1 सामने आए तो 0s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और 0s के साथ छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।
-
1 n 2 n -12, 1122, 111222 आदि। 1s की संख्या संख्या के बराबर है। 2s का। जब m 0 होता है तो हमारे पास कोई 0 नहीं होगा। 1s को पुश करते रहें और जैसे ही पहला 2 सामने आए फिर 1s पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और 1s के साथ छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।
-
0 n 1 m+n 2 m -0112, 001112, 001112 आदि। 1s की संख्या संख्या के योग के बराबर है। 0s और 2s के। जैसे ही पहला 1 सामने आता है, 0s को पुश करते रहें, फिर 0s को तब तक पॉप करें जब तक कि कोई 0s न बचे। अब फिर से 1s को तब तक पुश करें जब तक कि पहले 2 का सामना न हो जाए। फिर प्रत्येक 2 के लिए 1s को पॉप करना शुरू करें जब तक कि हमारे पास 1s न रह जाए। अगर हम अंत तक पहुँच जाते हैं और कोई 1 नहीं बचा है तो स्ट्रिंग स्वीकार कर ली जाती है।
-
NULL स्ट्रिंग भी स्वीकार की जाती है। 0 0 1 0 2 0
आइए मशीन को समझते हैं
-
राज्य 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 पर जाएं।
-