PDA (Pushdown Automata) पर लेक्चर नोट्स

परिचय

• Geet Smashers के इस वीडियो में आपका स्वागत है।
• PDA (Pushdown Automata) के महत्वपूर्ण बिंदुओं पर चर्चा की जाएगी।
• ये जानकारी प्रतियोगी परीक्षाओं और कॉलेज/यूनिवर्सिटी स्तर की परीक्षाओं के लिए फायदेमंद होगी।

Finite Automata की समीक्षा

• Finite Automata (DFA, NFA) को नियमित भाषाओं को पहचानने के लिए उपयोग किया जाता है।
• नियमित भाषाएँ शक्तिशाली होती हैं, लेकिन कुछ भाषाएँ ऐसी हैं जो नियमित भाषाओं से अधिक शक्तिशाली हैं।

उदाहरण

• उदाहरण: 0^n 1^n (जहाँ n >= 0)
  • केवल 0^n: Finite Automata द्वारा पहचानी जा सकती है।
  • 0^n 1^n: यह अधिक शक्तिशाली है क्योंकि इसमें 0 और 1 की संख्या बराबर होनी चाहिए।
  • यह एक तुलना की आवश्यकता है, जो Finite Automata द्वारा नहीं की जा सकती क्योंकि इसके पास सीमित स्मृति है।

PDA की आवश्यकता

• सीमित स्मृति के कारण, 0 और 1 की संख्या की तुलना करने के लिए अतिरिक्त स्मृति (स्टैक) की आवश्यकता होती है।
• Finite Automata के साथ स्टैक जोड़ने पर PDA बनता है।

PDA की विशेषताएँ

• PDA में पुश और पॉप ऑपरेशंस होते हैं।
• उदाहरण के लिए, 0 आने पर उसे स्टैक में डालें और 1 आने पर उसे पॉप करें।
• PDA नियमित भाषाओं के साथ-साथ संदर्भ-मुक्त भाषाओं (Context Free Languages) को पहचान सकता है।

PDA की औपचारिक परिभाषा

• PDA को परिभाषित करने के लिए 7 ट्यूपल्स का उपयोग होता है।
  1. Q: सीमित राज्यों का सेट
  2. Σ: इनपुट प्रतीकों का सेट
  3. Γ: स्टैक के प्रतीकों का सेट
  4. δ: संक्रमण कार्य
  5. q0: प्रारंभिक स्थिति
  6. Z0: स्टैक प्रारंभ प्रतीक
  7. F: अंतिम स्थिति का सेट

संक्रमण कार्य

• संक्रमण कार्य स्थिति, इनपुट प्रतीक, और स्टैक प्रतीक के आधार पर होता है।
• इनपुट और स्टैक प्रतीकों के आधार पर स्टैक में परिवर्तन किया जा सकता है।

स्टैक अनुप्रयोग

• स्टैक में प्रतीक जोड़ना और हटाना संभव है।
• स्टैक के शीर्ष पर Z0 प्रारंभिक प्रतीक के रूप में होता है।
• अंत में, यदि एक उचित संक्रमण होता है, तो स्टैक को अदृश्य करने के लिए संशोधित किया जा सकता है।

अंत

• PDA मॉडल कैसे काम करता है, इसे समझने के लिए आगे के उदाहरणों पर चर्चा की जाएगी।
• धन्यवाद!