पुशडाउन ऑटोमेटा परिचय

पीडीए की बुनियादी संरचना

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

मूल रूप से एक पुशडाउन ऑटोमेटन है -

"Finite state machine" + "a stack"

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

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

स्टैक हेड स्टैक के शीर्ष प्रतीक को स्कैन करता है।

एक स्टैक दो ऑपरेशन करता है -

Push - शीर्ष पर एक नया प्रतीक जोड़ा जाता है।
Pop - शीर्ष प्रतीक को पढ़ा और हटा दिया गया है।

एक पीडीए एक इनपुट प्रतीक को पढ़ या नहीं सकता है, लेकिन इसे हर संक्रमण में स्टैक के शीर्ष को पढ़ना होगा।

एक पीडीए को औपचारिक रूप से 7-ट्यूपल (Q, form, S, δ, q ₀ , I, F) के रूप में वर्णित किया जा सकता है -

Q राज्यों की परिमित संख्या है
∑ इनपुट वर्णमाला है
S स्टैक प्रतीक है
δ संक्रमण समारोह है: Q × (∑ transition {)}) × S × Q × S *
q₀प्रारंभिक अवस्था है (q ₀ ∈ Q)
I प्रारंभिक स्टैक शीर्ष प्रतीक है (I) S)
F राज्यों को स्वीकार करने का एक सेट है (F set Q)

निम्नलिखित चित्र एक पीडीए में राज्य क्यू ₁ से राज्य क्यू ₂ तक संक्रमण को दर्शाता है , जिसे ए, बी → सी - के रूप में लेबल किया गया है।

राज्य में इसका मतलब है q₁, अगर हम एक इनपुट स्ट्रिंग का सामना करते हैं ‘a’ और स्टैक का शीर्ष प्रतीक है ‘b’, तो हम पॉप ‘b’, धक्का दें ‘c’ ढेर के ऊपर और राज्य के लिए आगे बढ़ें q₂।

पीडीए से संबंधित शब्दावली

तात्कालिक विवरण

पीडीए का तात्कालिक विवरण (आईडी) एक ट्रिपल (क्यू, डब्ल्यू, एस) द्वारा दर्शाया जाता है जहां

q राज्य है
w गैर-इनपुट इनपुट है
s स्टैक सामग्री है

घूमने-फिरने की सूचना

"टर्नस्टाइल" नोटेशन का उपयोग आईडी के जोड़े को जोड़ने के लिए किया जाता है जो पीडीए के एक या कई चालों का प्रतिनिधित्व करते हैं। संक्रमण की प्रक्रिया को टर्नस्टाइल प्रतीक "den" द्वारा निरूपित किया जाता है।

एक पीडीए (क्यू, ∑, एस, q, क्यू ₀ , आई, एफ) पर विचार करें। एक संक्रमण को गणितीय रूप से निम्नलिखित घूमने वाले अंकन द्वारा दर्शाया जा सकता है -

(p, aw, Tβ) ⊢ (q, w, αb)

इसका तात्पर्य यह है कि राज्य से संक्रमण लेते समय p कहना q, इनपुट प्रतीक ‘a’ भस्म हो गया है, और ढेर के ऊपर ‘T’ एक नई स्ट्रिंग द्वारा प्रतिस्थापित किया जाता है ‘α’।

Note - अगर हम पीडीए के शून्य या अधिक चाल चाहते हैं, तो हमें इसके लिए प्रतीक (want *) का उपयोग करना होगा।