Pushdown automata (PDA) in Hindi

hello दोस्तों! आज मैं आपको इस post में what is Pushdown automata (PDA) in Hindi ( पुशडाउन ऑटोमेटा क्या है?) के बारें में बताऊंगा. यह theory of computation (TOC) का एक महत्वपूर्ण topic है तो चलिए start करते हैं:-

Table of Contents

Pushdown automata एक finite automata है जिसमें extra memory होती है जिसे stack कहते है. यह stack (स्टैक) pushdown automata को context-free language को पहचानने में मदद करता है.

PDA जो है वह context-free grammar को implement करने का तरीका है, वैसे ही जैसे हम regular grammar के लिए DFA को डिजाईन करते है. एक DFA जानकारी (information) की एक finite मात्रा को याद रख सकता है, लेकिन एक PDA जानकारी की infinite मात्रा को याद रख सकता है।

सामन्यतया एक pushdown automata (PDA) होता है:-

“Finite state machine” + “stack”

एक PDA के तीन components होते हैं:-

एक input tape
एक control unit
infinite size के साथ एक stack.

एक stack दो कार्य कर सकता है:-

Push – नए symbol को top में add करना.
POP – नए symbol को read करना तथा remove करना.

PDA, एक input symbol को या तो read कर सकता है या नहीं भी सकता है, लेकिन इसे हर transition में stack के top को read करना होता है।

image source

एक PDA को 7 tuple के द्वारा describe किया जाता है:- (Q, ∑, S, δ, q₀, I, F)

Q, states की finite संख्या है.
∑, इनपुट alphabet है.
S, stack symbol है.
δ, transition function है:- Q × (∑ ∪ {ε}) × S × Q × S*
q₀, शुरुवाती (initial) state है. (q₀∈ Q)
I, शुरुवाती स्टैक top symbol है. (I ∈ S)
F, accept की गयी states का एक समूह है. (F ∈ Q)

Instantaneous Description (ID)

ID एक informal notation है कि कैसे PDA एक input string की गणना करता है तथा यह निर्णय लेता है कि string को accept करना है या reject करना है.

एक PDA के instantaneous description को triplet (q, w, s) के द्वारा प्रस्तुत किया जाता है:-

q वर्तमान state है.
w बचे हुए input को describe करता है.
s, stack contents है.

Turnstile Notation

⊢ sign (चिन्ह) को turnstile notation कहते है. तथा यह एक move को प्रस्तुत करता है.

⊢* sign जो है वह moves के क्रम को प्रस्तुत करता है.

उदाहरण:- (p, b, T) ⊢ (q, w, s)

इसे भी पढ़ें:- finite automata क्या होता है?

निवेदन:- अगर आपके लिए यह आर्टिकल helpful रहा हो तो इसे अपने social media sites जैसे:- फेसबुक, whatsapp में अवश्य share कीजिये. जिससे कि अन्य लोगों की भी help हो पाए. और आपके इस post से related कोई question है तो नीचे कमेंट के द्वारा बता सकते हैं. thanks.