Hello दोस्तों, Geet Smashers, मैं आपका स्वागत हैं इस वीडियो में स्टार्ट करने जा रहे हैं PDA, that is Pushdown Automata और इस वीडियो में हम PDA से रिलेटिट सारा important point डिस्सेस करेंगे जो आपके competitive exams, even आपके college या university level के exams के लिए बहुत ज़्यादा beneficial होंगे तो guys फ़ड़ाफट से वीडियो को like कर दे, चैनल को subscribe करें अगर अब तक आपने नहीं किया है, please press the bell button ताकि आपको सारी latest notifications मिलती रहें तो start करते हैं PDA से सबसे पहले मैं आपको बता दूं, हमने डिस्सेस किया हुआ finite automata जिसमें हमने DFA, NFA के बारे में decision किया था and finite automata is used to recognize the regular language, अब regular language का क्या है, कि ठीक है they are powerful language, लेकिन अगर हमारे पास languages हैं, which are more powerful than regular languages तो उनके लिए जो है, वो finite automata recognize नहीं करेगा, तो मुझे और powerful machine चाहिए कैसे, let's see, अगर हम example लें, 0 power n 1 power n where n is greater than equal to 0 यहाँ पे हमारे पास language में क्या आ गया normal अगर मैं सिर्फ 0 power n लिखूँ मतलब number of zeros are what infinite तो यहाँ पे मैं कह सकता हूँ कि it is what recognized by the finite automata but 0 power n के बाद मैंने लगा दिया 1 power n तो यहाँ पे powerful क्यों कह रहे हैं हम इस language को यह इस language में extra चीज क्या है कि 0 जो है वो followed by 1 है and number of 0 and number of 1 are equal तो यहाँ पे number of 0 and number of 1 equal का मतलब क्या है यहाँ पे एक comparison आ गया तो जब भी एक comparison आ गया तो यहाँ पे finite automata fail हो जाएगा reason उसका क्या है finite automata के पास finite memory है अब finite memory में मैं finite value को जो है वो save कर सकता हूँ लेकिन मुझे बहुत सारी चीज़े हैं अगर मुझे इसको निकालना है, मतलब अगर मुझे इस language को recognize करना है, तो इसका logic क्या है, कि जितने zero आ रहे हैं, आप उनको count कर लो, उसके बाद जितने one आ रहे हैं, आप check कर लो, जितने zero आपने count किये थे, क्या one बराबर है या नहीं, अब ये सुनने में तो साह लग रहा है तो इस काम को करने के लिए मेरी finite जो memory है वो sufficient नहीं है मुझे extra memory चाहिए, extra stack चाहिए और वो जब मैं लगा दूँगा तो ये मेरा बन जाएगा और powerful machine बन जाएगी मतलब finite automata में हमारे पास finite memory थी तो finite memory से हम काफी languages को accept कर सकते हैं but all languages are regular language बट अगर language regular नहीं है तो उस case में मेरे को ज़्यादा powerful machine चाहिए और powerful बनाने के लिए हमने किया क्या? कोई extra कोई power नहीं दी, हमने simple क्या किया? finite automata के साथ में हमने एक stack add कर दिया finite automata के साथ में जब हम stack को add कर देते हैं तो यह बन जाता है PDA, that is push down a automata push down का मतलब क्या है?
यहाँ पे हम stack use कर रहे हैं तो obviously यहाँ पे push operation, pop operation होंगे अब यहाँ पे logic क्या चल रहा है? 0, 0, 1, 1 देखो अब जब भी जीरो आईगी, मतलब मेरे इनको count करने की कितनी बार जीरो आई, तो मैं क्या कर सकता हूँ, जैसे जीरो आई, मैंने stack में डाल दी, जैसे जीरो आई, मैंने stack में डाल दी, जैसे जीरो आई, मैंने stack में डाल दी, अब उसके बाद जैसे वन आया, हर एक वन के लि� मेरा epsilon बचा, मतलब कोई 0 या 1 कुछ नहीं बचा, तो obviously आप कह सकते हो कि number of 0 and 1 क्या है, बराबर, लेकिन यह कब possible हुआ, अगर आप एक extra memory, एक extra stack इसके अंदर add कर दो, तो जब भी हम finite automata में stack add कर देते हैं, that becomes the PDA, तो obviously अगर आप से पूछे कि PDA is more powerful, yes, PDA is more powerful than the finite automata, क्योंकि PDA finite automata का काम तो करी रहे हैं, मतलब regular languages को तो accept करी रहे हैं, बट साथ साथ regular languages से ज़्यादा जो powerful languages हैं, जिनके अंदर हम single comparison, जैसे 0 power n, 1 power n, या फिर w, w, r, मतलब palindrome, जितनी मेरे पास string आई, उसका reverse, अब obviously पहले मेरे पास string आई, उसका reverse find out करने के लिए, obviously मेरे को कहीं न कहीं storage extra चाहिए, तो जितनी भी इस type की languages हैं, इनको बोलते हैं context free languages, तो context free languages को recognize करने के लिए हम use करते हैं, PDA, that is Push Down Automata. तो अब हम बात करें यहाँ पे इसकी Formal Definition.
तो Formal Definition में हमारे पास 1, 2, 3, 4, 5, 6, 7 कितने tuples हैं? 7 tuples को हम use करते हैं to define the Push Down Automata, जिसमें से कुछ आपके Finite Automata, वाले ही है जैसे Q, that is a finite set of states like finite automata, जैसे finite automata में set of states हमारे पास होती है finite, ऐसे ही हमारे पास यह है, जिसमें Q0, Q1, final state, बहुत सारी हो सकती है, then हमारे पास आता है input symbol, जैसे finite automata में हम 0, 1, या फिर A, B, input symbol लेते थे, ऐसे ही इसमें लेंगे, यह नहीं चीज़ है, that is tau, tau यहाँ stack के अंदर आप कौन सी alphabet को push कर रहे हो, 0 को कर रहे हो, 1 को कर रहे हो, जैसे इस case में देखो, अब इस case में हमारे पास, यह वाला जो case है, 0 power n, 1 power n, इसमें देखो, input symbol कौन से है, 0 है, 1 है, बट इसका मतलब यह नहीं है कि आप 0 भी push करोगे, आप 1 भी push करोगे, simple सा logic है, आप 0 push करो, 1 आपके यहाँ पे हैं ही, मतलब यह जो finite automata की memory इसमें, अलड़ी हमारे पास input string में, अलड़ी 1 पड़े है, तो हर एक 1 के लिए 0 को pop कर दो, तो आपका question जो है, वो solve हो जाएगा, तो यानि tau क्या कहता है, कि जो element, या जो input, हम stack के अंदर डाल रहे हैं, that is become the tau, तो ऐसा जुरूर नहीं है, कि सारे input symbol ही डालेंगे, obviously आपका जो है, depends on the question की, कि इस question में क्या बनना, सिर्फ 0 ही आपका push होगा, आपका 1 यहाँ पे push नहीं होगा, transition function, इस बार बहुत इंपोर्टेंट है। पर अगर आपको एक एक्शन फंक्शन के बारे में बात करेंगे, तो आप इस बार बहुत इंच बात करेंगे। लेकिन आप इस तरीके से इस तरीके से ले सकते हैं। क्योंकि एक्शन फंक्शन में हमारे पास क्योंकि आपका विशेष है। और इसमें हम दिया क्या है। इस सिंबल में जीरो वन एबी के साथ साथ हमारे पास एप्साइलम भी हो सकता है, तो एप्साइलम के case में भी यह चलेगा, और टाउ, टाउ मतलब stack में क्या symbol है, तो आप कह सकते हो कि जो transition होगी, transition होती क्या है, एक state से दूसरी state में jump करना, एक state से दूसरी state में जाना, तो वो transition किसके उपर depend कर रही है, एक तो आपकी current state क्या है, द इन तीनों के ऊपर डिपेंड करती है, तो अगर आपसे कोई भी question बुज़ से है, कितनी चीजों के ऊपर डिपेंड कर रही है, तो इन तीन चीजों के ऊपर डिपेंड कर रही है, मतलब तीन argument हम pass करेंगे input में, और output क्या आ रही है, q into tau star, और output में हमारे पास क्या आ रहा है, Q0 that is your initial state, मतलब initially आप कौन सी state से चलो, जब हम state diagram बनाएंगे, वहाँ पे आपको clear हो जाएगा, then Z0 that is a stack start symbol, यहाँ पे जो हम stack लेके चल रहे हैं, तो stack में by default top of the stack जो है, वो क्या denote कर रहा है, Z0, by default top of the stack जो है, वो Z0, Z0 क्या है, एक हमने symbol define कर दिया, जो stack के अंदर by default रहेगा, इसके लावा आप जब 0, 1, 0, 1 डालते जाओगे जो भी आप value डालोगे तो top of the stack के basis पे आप values put करते जाओगे तो top of the stack आपको by default बताता रहेगा कि कहाँ पे आपको value डाल लिये तो आपको पुश करते जाओगे और पॉफ करेंगे तो top of the stack नीचे की तरफ आएगा जब पुश करेंगे तो top of the stack उपर की तरफ जाता जाएगा तो हमारे पास आता final state तो आपको पुश करेंगे तो top of the stack उपर की तरफ जाता जाएगा final state, but याद रखना, PDA में जरूरी नहीं हो भी सकता कि final state हो, हो सकता कि final state ना हो, तो यह main points are related to the PDA, यहाँ पे last में जो मैं आपको point बता दू, कि अगर यह tau और यह वाली value, मतलब, जब हम transition function की जो values हैं, वो हम लिखेंगे, उसके बेस पे आपको और ज़्यादा clear होगा, लेकिन यहाँ पे तीन ही आपके जो main point बनते हैं, अगर यह symbol और यह symbol, दोनों symbol अगर यहाँ पे बराबर हैं, मतलब ये और ये symbol अगर बराबर है आपके पास कोई भी transition function दिया हो properly अगर ये दोनों symbol बराबर है तो आपका जो stack होगा वो क्या होगा unchanged होगा मतलब कोई उसमें change है नहीं करना अगर ये वाला symbol आपका epsilon है या lambda है null है तो उस case में क्या करना है आपको ये वाला symbol क्या कर देना है pop कर देना based on the question आपको यहाँ पर उसको क्या कर देना है पॉप कर देना है और तीसरा case क्या है अगर दोनों के दोनों symbol क्या होंगे अलग लगोंगे मतलब यहाँ पर let's suppose 0 है यहाँ पर let's suppose Z not है यहाँ पर let's suppose 1 है अगर अलग लग है तो उस case में आपको क्या करना है यह वाला symbol जो है वो push कर देना है जो भी यहाँ पर होगा stack के अंदर push कर दो अगर यहाँ पर यह वाला टाओ जो है वो यह सिर्फ epsilon denote कर रहा है तो उस case में आपको यह symbol को pop करना है और अगर दोनों बराबर है यह वाले symbol तो आपको उस case में no change करना है मतलब जो stack है उसको as it is रहना है तो यह model जो है वो कैसे काम करता है बस finite automatic जो भी string हमने चलनी है एक एक करके read write head जो है वो read करता रहेगा इस read write head से सिर्फ यहाँ पे हमारे पास read operation होगा, right नहीं होगा, मतलब कुछ chain नहीं कर सकते, यह सिर्फ read करता रहेगा, और आगे आगे जाता रहेगा, और last में हमारे पास जो है वो, जब string घतम हो जाएगी, तो last symbol कौन सा होगा, epsilon, और stack जो है, वो stack के अंदर हम values को push भी कर सकते हैं, stack से हम value को pop भी कर सकते हैं, this is how the model of PDA will work, जब हम next video में इसके related example discuss करेंगे, thank you.