हमें एक भाषा "L" दी गई है और कार्य दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा का निर्माण करना है जो बताता है कि वर्ण 'a' की आवृत्ति घटना के समय से दोगुनी होनी चाहिए वर्ण 'बी' और वर्ण 'सी' की घटनाओं को 'डी' के समय चौगुना होना चाहिए और सभी वर्णों की घटनाएं न्यूनतम 1 होनी चाहिए जो स्ट्रिंग को न्यूल भी बना सकती है और इसे ऑटोमेटा द्वारा स्वीकार किया जाना चाहिए। पी>
पुशडाउन ऑटोमेटा क्या है?
एक पुशडाउन ऑटोमेटा या पुशडाउन ऑटोमेटन या पीडीए एक संदर्भ-मुक्त व्याकरण को लागू करने की एक तकनीक है जिस तरह से हम एक नियमित व्याकरण के लिए नियतात्मक परिमित ऑटोमेटन या डीएफए डिजाइन करते हैं। एक डीएफए परिमित डेटा पर काम कर सकता है, लेकिन एक पीडीए अनंत डेटा पर काम कर सकता है। हम पुशडाउन ऑटोमेटा को "परिमित स्टेटमशीन" और "स्टैक" के संयोजन के रूप में समझ सकते हैं।
एक पुशडाउन ऑटोमेटन में तीन घटक होते हैं -
-
एक इनपुट टेप,
-
एक नियंत्रण इकाई, और
-
अनंत आकार वाला ढेर।
एक PDA को औपचारिक रूप से 7−tuple (Q, Σ, S, , q0, I, F) -
के रूप में वर्णित किया जा सकता है।-
Q राज्यों की परिमित संख्या है
-
Σ इनपुट वर्णमाला है
-
S स्टैक सिंबल है
-
δ संक्रमण फलन है:Q × (Σ {ε}) × S × Q × S*
-
q0 प्रारंभिक अवस्था है (q0 Q)
-
I प्रारंभिक स्टैक शीर्ष प्रतीक है (I Ε S)
-
F, स्वीकार करने वाली अवस्थाओं का एक समूह है (F Ε Q)
आइए दी गई भाषा के लिए एक पुशडाउन ऑटोमेटा बनाएं -
इस पीडीए द्वारा स्वीकार्य स्ट्रिंग्स फॉर्म के हैं -
-
c 4n डी n - ccccd, ccccccccdd, आदि। cs की संख्या संख्या का 4 गुना है। डी.एस. का जब m 0 होता है तो हमारे पास कोई as और bs नहीं होगा। cs को पुश करते रहें और जैसे ही पहला d सामने आए फिर स्टैक से 4 c पॉप करें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और बिना cs के छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।
-
a 2m बी एम - आब, आआब, आदि। जैसा कि संख्या का 2 गुना है। बी.एस. का जब n 0 होता है तो हमारे पास कोई cs और ds नहीं होगा। जैसे ही पहला बी सामने आता है और फिर स्टैक से पॉप 2 बी दबाते रहें। यदि हम स्ट्रिंग के अंत तक पहुँचते हैं और बिना किसी के छोड़ दिया जाता है तो स्ट्रिंग स्वीकार कर ली जाती है।
-
a 2m c 4n डी n बी एम - aaccccdb, aaaccccccccddbb। के रूप में की संख्या 2 गुना है। bs और cs की संख्या ds की संख्या के 4 गुना के बराबर है। के रूप में और सीएस को आगे बढ़ाते रहें। जैसे ही पहला d सामने आता है तो 4 cs को पॉप करें यदि वह शीर्ष पर है और फिर बाकी bs के लिए 2 पॉप करें। यदि हम अंत तक पहुँच जाते हैं और कोई a नहीं बचा है तो स्ट्रिंग स्वीकार कर ली जाती है।
-
NULL स्ट्रिंग भी स्वीकार की जाती है। ए 0 ग 0 घ 0 बी 0 ।
आइए मशीन को समझते हैं
-
राज्य q0 के लिए संक्रमण -
-
( a, I/a,I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक a है तो स्टैक के शीर्ष पर a को पुश करें और q0 पर बने रहें। स्टैक एआई बन जाता है…
-
( c, I/c,I ) - यदि स्टैक का शीर्ष I है और वर्तमान इनपुट प्रतीक c है तो c को स्टैक के शीर्ष पर धकेलें और q0 पर बने रहें। स्टैक सीआई बन जाता है...
-
( a, a/a,a ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक भी a है, तो a को स्टैक के शीर्ष पर धकेलें और q0 पर बने रहें। स्टैक आ जाता है... अगले c या b तक पुश करते रहें।
-
( c, c/c, c ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक भी c है तो c को स्टैक के शीर्ष पर धकेलें और q0 पर बने रहें। स्टैक cc बन जाता है.... cs को अगले d तक पुश करते रहें।
-
( b, a/e,aa ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक b है तो स्टैक से 2 पॉप करें और q3 पर जाएं।
-
(c, a/c,a ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक c है, तो c को स्टैक के शीर्ष पर धकेलें और q1 पर जाएँ। स्टैक सीए बन जाता है...
-
( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q4 पर जाएं।
-
($, I/I, I) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ न करें और q5 पर जाएं। NULL स्ट्रिंग के लिए।
-
-
राज्य q1 के लिए संक्रमण -
-
( c, c/c,c ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक भी c है तो c को स्टैक के शीर्ष पर धकेलें और q1 पर बने रहें। स्टैक cc बन जाता है.... cs को अगले d तक पुश करते रहें।
-
( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q2 पर जाएं।
-
-
राज्य q2 के लिए संक्रमण -
-
( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q2 पर जाएं।
-
( b, a/e,aa ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक b है तो स्टैक से 2 पॉप करें और q3 पर जाएं।
-
-
राज्य q3 के लिए संक्रमण -
-
( b, a/e,aa ) - यदि स्टैक का शीर्ष a है और वर्तमान इनपुट प्रतीक b है तो स्टैक से 2 पॉप करें और q3 पर बने रहें।
-
( $, I/I, I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और q5 पर जाएं। NULL स्ट्रिंग के लिए।
-
-
राज्य q4 के लिए संक्रमण -
-
( d, c/e,cccc ) - यदि स्टैक का शीर्ष c है और वर्तमान इनपुट प्रतीक d है तो स्टैक से 4 ds पॉप करें और q4 पर बने रहें।
-
( $, I/I, I ) - यदि स्टैक का शीर्ष I है और कोई इनपुट नहीं है तो कुछ भी न करें और q5 पर जाएं। NULL स्ट्रिंग के लिए।
-