[0:00]Hello dosto, Gate Smashers mein aapka swagat hai. Is video mein main explain karne ja raha hu DFA that is Deterministic Finite Automata aur isse related saare important points discuss karne ja raha hu jo aapke competitive exams even aapke college ya university level ke exams ke liye bahut zyada beneficial honge.
[0:16]To guys fatafat se video ko like kar dein channel ko subscribe karein agar ab tak aapne nahi kiya and please press the bell button taaki aapko saare latest notifications milti rahein. To start karte hain DFA that is Deterministic Finite Automata. Ab isme sabse pehla important point main aapko bata du, deterministic ka matlab kya hai? Deterministic ka matlab yahan pe kya hai ki agar mere paas automata ke andar ek state hai q0 aur q0 pe main koi bhi string apply kiya, q0 pe main koi bhi alphabet apply kiya, let's say main apply kiya A. Chahe A karo B, C, koi bhi alphabet apply kiya. Toh yeh ek particular state pe jayega. Ab woh state kaunsi hogi? Q1 bhi ho sakti hai, Q2 bhi ho sakti hai, QN ho sakti hai, Q0 bhi ho sakti hai lekin ek state hogi yeh fixed hai. Aur jahan pe yeh cheez fixed ho jaye, usko bolte hain hum deterministic. Jo ki NFA ke case mein nahi hota hai kyuki NFA ke case mein hamare paas Q1 pe bhi jaa sakti hai Q2 pe bhi jayegi, Q3 pe. Multiple states mein bhi jaa sakta hai. Ho sakta hai woh null state mein jaaye, ho sakta hai matlab kisi bhi state pe na jaaye toh yeh multiple choices hoti hain NFA ke case mein lekin Deterministic Finite Automata ka matlab hai ki agar aap ek state pe koi bhi alphabet apply karte ho toh woh aapko kisi na kisi particular single state pe leke jayega.
[1:36]Toh yeh funda hai deterministic ka. Aur automata kya hai? Automata humne already discuss kiya hua hai ki automata ko hum kya bol rahe hain? Ek machine hai jo actual mein language ke representation ko yahan pe hum use kar rahe hain. Matlab language ko agar humne standard way se represent karna hai chahe meri language finite hai chahe meri language infinite hai agar mujhe usko represent karna hai toh main kya use karta hu? Automata ko use karta hu. Toh automata ek machine hai, ek abstract model hai jo actual mein batati hai ki kya yeh language accept hogi ya yeh language accept nahi hogi. Toh isko bolte hain hum kya actual mein Deterministic Finite Automata. Aur DFA ko hum denote kaise karte hain? DFA ko hum denote karte hain in paanch symbols se in paanch tuple se hum actually denote karte hain. Toh isko actual mein hum yahan pe kya bol rahe hain? Sabse pehle hai Q. Capital Q ka yahan pe matlab kya hai? Set of all finite states. Matlab aapki machine ke andar kaun kaunsi states hongi? States ka matlab kya hai ki ek state matlab starting state se output mein jaane ke liye aapne kitni beech mein transitions ki, kitni states pe aap gaye, toh woh saari states ki collection ko hum Q bolte hain. Then hamare paas aata hai yahan pe summation. Yeh hai actual mein kya? Yeh main already discuss kiya hua hai. Yeh hai alphabet, set of alphabet. Let's suppose jo hum common lete hain jaise hum lete hain A aur B. Matlab A pe kahan ja raha hai B pe kahan ja raha hai, 0 aur 1 bhi le lete hain lekin most of the time hum A aur B alphabet ko use karte hain. Then hamare paas aata hai delta. Yeh hai actual mein kya transition.
[3:18]Transition ka matlab kya hai ki aapne ek state pe koi bhi alphabet apply kiya A ya B aap kahan gaye matlab aap kahan pe pahunch gaye? Uski output kya hai? Aap kis state pe reach kar jaoge toh is transition ko actual mein bolte hain. Ek state se dusri state mein transition karna woh actual mein kaise denote karte hain delta se. Then q0 q0 hai aapki start start state matlab aapne start kaunsi state se kiya hai? Woh hoti hai hamari generally q0 aur F kya hai? Set of finite final state. Ab kehne ka matlab yahan pe kya hai ki generally hamare paas final state hum ek hi likh ke chalte hain. Final state matlab jahan pe aapke jaa ke string jo hai woh complete ho jayegi. Matlab jahan pe jaa ke aapka jo hai output generate hoga woh hogi aapki final state. Lekin kai baar hamare paas multiple final states bhi possible hain toh isko hum generally kya likh dete hain set of all final states. Lekin jitni bhi final states hongi woh yaad rakhna total states aapke paas kitni hai Q toh yani final state jo hongi woh subset hoga kiska Q ka. Obvious hai. Final state jo hai woh Q se zyada toh ho hi nahi sakti. Q kya hai? Set of all states. Jitni bhi states hain woh hai Q toh final state ya toh maximum se maximum Q matlab saari ki saari final state hai. Otherwise kuch na kuch kam hongi toh aap keh sakte ho ki F is a subset of all states that is Q. Kai baar is point, yeh chhote chhote points na competitive exams mein theory ke point of view se bhi pooche ja sakte hain. Toh aapko yeh points jo hai woh yaad hone chahiye. Kyuki DFA one of the most important topic hai TOC ka. Kyuki maximum question aapko competitive exams mein DFA ke related hi aate hain. DFA hota kya hai, kyu hum use karte hain, kaise hum use karte hain aur usko baad mein design karna. Jo hum next videos mein discuss karenge. Toh yahan pe yeh ho gaya in paancho ki jo hai basic definition ki yeh DFA ko hum denote kaise karte hain. Toh in paanch symbols se hum isko denote karte hain. Ab ek simple sa example lete hain hum. Let's suppose mujhe ek DFA banana hai. Mujhe ek Deterministic Finite Automata banana hai for a language. Kis language ke liye? Jismein saari strings should be starting with A. Matlab woh language mujhe yahan pe likhni hai jiske andar saari strings kyuki language jo hai woh collection of strings hai. Matlab aapko woh saari strings aani chahiye jiska starting letter kya ho? A ho. Toh yani agar main iski language likhu toh kaise likhoge? Sabse minimum string kaunsi hogi? Sabse chhoti se chhoti A itself hi hogi. Dekho A ke andar starting kya hai? A hi toh hai toh A se chhoti koi ho nahi sakti. Iske alawa AA bhi ho sakti hai. AAA bhi ho sakti hai. Aise jitna marzi badhate raho. AB bhi ho sakti hai. ABB bhi ho sakti hai. ABAB bhi ho sakti hai. Multiple jo hai woh possibility hai. But kya BA ho sakti hai? Nahi. Yeh aapko dhyaan rakhna hai. Dekho starting letter B ho gaya yani is type ke jo hain woh strings nahi hone chahiye. Toh yani yeh actual mein kya? Start with A. Toh yani yeh obviously finite hai ya infinite? Yeh infinite language ka part hai. Ab is infinite language ko mujhe represent karna hai with the help of finite automata. Kaise karenge? Let's start with the designing part. Toh design karte hain. Sabse pehle hamare paas kya hai? Q0 that is a initial state. Toh starting state ya initial state ko hum aise denote karte hain Q0. Matlab multiple bhi ho sakta hai. Kahi jagah pe yahan pe ABC mein bhi denote kar dete hain, XYZ toh koi ghabrane ki zarurat nahi hai. General notation hamare paas Q0 hai aur yeh yeh jo teer humne yahan pe lagaya hai yeh arrow lagaya hai, yeh actual mein batata hai ki yeh start state hai. Yahan se start kar rahe hain. Ab mere ko chahiye A. Matlab kam se kam jab bhi aap DFA design karo na hamesha yaad rakhna, aap minimum se minimum string ke liye design kar lo pehle uske baad filling the blanks kar lena. Filling the blanks ka matlab kya hai?
[8:03]Ki kya yeh DFA hai? Nahi. Yeh DFA kyu nahi hai? Iska reason actual mein kya hai? Yeh DFA isliye nahi hai kyuki har ek DFA mein agar main alphabet ki baat karu toh let's suppose is question mein hamare paas jo alphabet hain woh hai A aur B. Toh dekho Q0 A ke liye toh idhar chali gayi. But B ke liye kahan ja rahi hai? B ke liye toh humne denote hi nahi kiya toh mujhe saari, saare ke saare alphabet ke liye denote karna padega. Toh A ke liye Q0 yahan ja rahi hai B ke liye kahan jayegi? Agar main B yahan bana deta hu. Let's suppose agar main B yahan bana deta hu toh mera question galat ho gaya. Kyuki starting mein agar B aa gaya toh B bhi accept ho jayega. Toh yani main B ko yahan toh nahi likh sakta. Dusra case kya ho sakta hai? Let's suppose maine self loop bana diya B ka. Agar main self loop bana du B ko toh dekho agar string aati hai BA toh dekho BA kaise chalana hai aapko? Starting se B aaya. B aate hi Q0 se hum Q0 pe hi rahe aur A aate hi hum yahan pe pahunch gaye toh yeh toh accept ho gayi. Lekin humne BA ko accept nahi karwana. Starting mein A hi aana chahiye. Toh iska matlab kya hai? Self loop bhi nahi ban sakta aur na B yahan pe likh sakte. Toh obviously mujhe B ko trap karna padega. Matlab B ko mujhe dead state mein jana padega. Taaki main wahan se wapis hi na aa saku toh isko bolte hain hum trap. Matlab humne B ke liye ek state bana di let's say Q0 aur B jab bhi aayega woh Q0 pe chala jayega. Q0 se woh kahin nahi ja sakta. Matlab there is no path to reach to the final state. Isko bolte hain hum trap kar diya humne isko. Isko dead state mein shift kar diya. Toh dead state mein isko humne bana diya. Ab dekho Q0 A pe idhar jaa rahi hai, B pe idhar jaa rahi hai, lekin Q1 Q1 kahan jaa rahi hai? Q1 ka toh na A pe banaya na B pe banaya toh koi dikkat nahi hai. Aap A aur B pe simple bana do. Kaise aaya? Yeh mind mein kaise aayega ki A aur B ko aapko self loop mein banana hai? Dekho starting letter A hai. A ke baad kya hai? A ke baad kuch marzi ho, A ke baad A ho, A ke baad B ho, BB ho, AA ho, jitne marzi koi bhi combination. Toh dekho starting mein jab jaise hi A aaya main yahan pahunch gaya. Ab uske baad AA aata hai accept hoga, AB aata hai, ABB aata hai, jo marzi aaye woh kya honge? Accept honge. Hamari jo condition hai ki first letter A hona chahiye woh meri true hogi. Aur dekho Q0 Q0 ko B aap simple A aur B ke liye isi pe bana do. Kyuki agar aap galti se isko upar le jaoge ya idhar leke jaoge toh yeh jo hai woh dead state nahi rahegi. Phir koi aur ho sakta hai aisi input jismein A starting mein na aa raha ho woh bhi accept ho jaaye. Toh dead state mein hamesha A aur B khud pe hi jaata hai taaki isko hum trap rakh sakein. Isse bahar nahi aa sakte, na isse kahin aur jaa sakte. Toh yeh aapka ban gaya kya DFA kyuki Q0 aapka A pe idhar jaa raha hai, B pe idhar jaa raha hai. Q2 A aur B pe idhar jaa raha hai yeh bhi fine ho gaya. Q1 A aur B pe idhar jaa raha hai toh yeh bhi fine ho gaya toh ab aapka DFA taiyar ho gaya. Toh isko bolte hain hum transitions. Transition ka matlab kya hai? Transition ko hum denote karte hain is tarike se. Transition ka matlab kya hota hai? Q into yeh aapka ho gaya summation matlab aapke jo alphabet hain that is A and B and it is what? Representing the Q isko hum represent karte hain delta ko hum represent karte hain is tarike se.
[11:20]Iska matlab kya hai? Q aapke paas kya hai? Saari states. Kaun kaunsi states hain? Q0, Q1, Q2. Aur isko multiply kar do kisse? Q0 Q1 Q2. Toh agar aap is dono ko multiply karoge toh kya aayega? In dono ko agar hum multiply karoge toh yeh aa jayega Q0 A, Q0 B, Q1 A, Q1 B, Q2 A, Q2 B. Simple humne cross multiply kar diya. Dono ko humne cross multiply kar diya. Toh yeh 3 into 2, 6 apne paas states ban gayi. Toh is 6 states ko humne kya karna hai ab Q. Q yahan pe kya hai? Q0 Q1 Q2. Toh dekho kaise represent karoge? Q0 A aata hai. Q0 ke upar agar A aata hai toh aap kahan jaoge? Q1 pe jaoge.
[12:20]Toh isko aap aise denote kar do yeh aapka transition banta ja raha hai. Q0 pe agar B aata hai. Q0 pe B aata hai toh aap Q2 pe chale jaoge. Toh Q2 pe bana do. Then Q1 pe agar A aata hai toh aap Q1 pe hi ho. Q1 pe agar A aata hai toh aap kahan pahunchoge? Kahin nahi pahunchoge aap Q1 pe hi rahoge. Aise hi Q1 pe agar B aata hai toh aap Q1 pe B aate hi aap kahan pahunchoge? Aap Q1 pe hi rahoge. Aise hi agar Q2 pe A aata hai toh dekho aap Q2 pe rahoge. Q2 pe agar B aata hai toh dekho aap Q2 pe hi rahoge. Toh yeh actual mein hai funda represent karne ka transitions ko. Toh Q1 aapka Q0, Q1 aur Q2 jo hai is tarike se aapka complete hota hai. Toh yeh actual mein kya hai? Transitions jisko hum bolte hain ki ek state pe agar main alphabet apply karta hu toh aap kis jagah pe pahunchoge that is called the transition. Toh yeh paancho tuples jo hai paancho symbols aapko clear ho gaye.
[13:06]Aur yeh basic sa example hai starting with A, Deterministic Finite Automata ka. So this is all important points related to the DFA. Thank you.
