Deterministic Finite Automata (Example 4)

[@Laeyz]

'whatever happens in dead state , stays in dead state.' sounds familiar.

[@lightbinger]

I was writing same and saw your comment.

[@sarthakpatel107]

'Whatever happens in Green mile, stays in green mile.'

[@himanshushukla6451]

@@sarthakpatel107 or area 52

[@tamamshud5879]

People who ghost others do be like that

[@skyadav8842]

Vegas

[@mohammad_a_razeq2526]

This channel is really beautiful and very useful , thank's for your effforts

[@curtispatrick8072]

Great aid, but I think this one has a couple of problems. 1. (D) should transition to self on {0,1} because you've matched on the '1 followed by 0'. 2. (C) on {0} should transition to another state, (F) because while '00' will never match the '01' rule, it *might* match the '1 followed by 0' rule. (F) would transition to itself (F) on '0', but transition to (B) on 1. Of course, I could be wrong. I'm here because I'm looking at ANTLR and it talked about DFA and NFA and I have found these tutorials really useful, easy to consume, and easy to remember.

[@vishalkumarjha3368]

Here, the string 1111....10 (at least one 1 followed by 0 is not assumed to be a sub string, it just is at least one 1 followed by one 0. ) For instance, 1110 will be accepted . But 11101 or 11100 will be rejected. So, stage D has to transition to Stage X to ensure rejection of the above mentioned strings. If stage D transitions to D itself, then 11101 and 11100 will both be accepted . If the case was that at least one 1 followed by a 0 was a sub-string(for example 11100 or 11101) then D should have transitioned to itself on 0 and 1 .

[@vishalkumarjha3368]

The same goes for your second argument. The question is not about 01 or 111...10 being sub-strings . It either exactly has to be 01 or 111.....10 (n number of 1s followed by a 0, where n=1,2,3....).

[@vishalkumarjha3368]

Although, there's a problem of clarity in the statement. The fact that it has not to be a sub string could have been stated better. L = {Accepts the string 01 or a string of at least one 1 ended by exactly one 0.} This could have been a more clear representation of the DFA.

[@vipuljha1818]

@@vishalkumarjha3368your machine will accept 1010 and also 010. So I think the correct answer is L= "accepts the string 01 or a string of atleast one '1' ended with single occurring 0"

[@fukovskipls]

@@vipuljha1818 Neither 1010 nor 010 are accepted due to going to the dead state

[@soniaasghar1094]

FAbulous way of teaching

[@jonaandgoshkoarebored7865]

mesmerizing indeed

[@haoranchang262]

I would say D should not go to the dead state. Because when you are in state D, which means there IS at least one '1' followed by a 'zero'. So no matter what the rest of the string looks like, it should be accepted.

[@fimboaloha8535]

I have the same question as you.

[@vishalkumarjha3368]

@@fimboaloha8535 Here, the string 1111....10 (at least one 1 followed by 0 is not assumed to be a sub string, it just is at least one 1 followed by one 0. ) For instance, 1110 will be accepted . But 11101 or 11100 will be rejected. So, stage D has to transition to Stage X to ensure rejection of the above mentioned strings. If stage D transitions to D itself, then 11101 and 11100 will both be accepted . If the case was that at least one 1 followed by a 0 was a sub-string(for example 11100 or 11101) then D should have transitioned to itself on 0 and 1 . The question is not about 01 or 111...10 being sub-strings . It either exactly has to be 01 or 111.....10 (n number of 1s followed by a 0, where n=1,2,3....). So, basically 1110 accepted. 11101 rejected. 11100 rejected. 01 accepted. 010 rejected. 010101 rejected . As we can see, the examples which have been rejected above have 1110 and 01 as sub strings , but since they are not the complete strings, they are rejected. That's the demand of the question.

[@01aniruddhaislam26]

@@vishalkumarjha3368 thanks for the explanation.

[@arpitadaspoddar4336]

I think the language will be like dfa accepts the string 01 or a string starting with atleast one 1 followed by 0. other wise the string 010 has atleast one 1 followed by 0, but 010 is not accepted according to dfa.

[@shivendrayadav3991]

i think it accepts only 01 and 1 followed by 0.

[@mahmoudtarek7854]

The 1 followed by 0 must be at the beginning of the string, so 010 is not accepted.

[@themuchy1]

"Accepts the string '01', the string '10' or a string that starts with '1' followed by any number of '1's and a single '0' at the end"

[@AliAhmed-gg1tz]

yeh bharwa fail karady ga tumhen

[@mahnoorahmed8723]

It accepts all the strings with "atleast digit 1 followed by 0" or "01" so it doesn't matter what comes before 01 or after 01, it will accept it! So 0'01', '01'0 and '01'1 is acceptable. Same goes for the first situation too. We have to identify ouselves whether the string is from first situation or from second.

[@nehatadam6904]

The state transition diagram is not complete. DFA is a machine for which every state must contain transition for every input symbol and single transition per input symbol.

[@AlexAkira-yd4nk]

Thank you for the remark. I thought the state should be UNDEFINED, but your comment corrected my misconception.

[@ShishiraNataraj]

it is corrected by adding a dead state in the second half of the video

[@pankhanafis818]

@@ShishiraNataraj well he shouldve added the dead state from the very beginning....since he already explained what a dead state is in the earlier videos......It would prevent unnecessary confusions and climaxes

[@buflen]

He knows. Don't worry. That's why you should look the whole video before commenting.

[@NeerajKrGupta-ys2ey]

@Neha Tadam firstly watch complete video then only come to a conclusion

[@Ali_Alhajji]

So what this DFA does is : 1) Accepts 01 2) Accepts all strings that start with a sequence of 1s followed by a single 0.

[@chilledout6738]

it doesnt have to start with 1

[@adityakaran]

L={01, 1*0}

[@NewtonMD]

A DFA must have a transition for all symbols for all states. That was not a DFA from the beginning, and adding states to the automaton changes it from the original, which was not a dfa

[@omarmarnissi1458]

well that's incorrect

[@parasytea]

@@omarmarnissi1458 why ?

[@ritvikreddy3959]

What does dfa say ? It should have states and transitions with only single path for specific inputs. The diagram at the start of the video was a dfa but it wasn't complete because it didn't correctly explain what would happen if c gets the input 0 and if final states get the input 0,1. But at the end of the video he added dead states but the language wasn't clear due to which there was a lot of confusion in comment section.

[@vishalkumarjha3368]

Here, the string 1111....10 (at least one 1 followed by 0 is not assumed to be a sub string, it just is at least one 1 followed by one 0. ) For instance, 1110 will be accepted . But 11101 or 11100 will be rejected. So, stage D has to transition to Stage X to ensure rejection of the above mentioned strings. If stage D transitions to D itself, then 11101 and 11100 will both be accepted . If the case was that at least one 1 followed by a 0 was a sub-string(for example 11100 or 11101) then D should have transitioned to itself on 0 and 1 . The question is not about 01 or 111...10 being sub-strings . It either exactly has to be 01 or 111.....10 (n number of 1s followed by a 0, where n=1,2,3....). So, basically 1110 accepted. 11101 rejected. 11100 rejected. 01 accepted. 010 rejected. 010101 rejected . As we can see, the examples which have been rejected above have 1110 and 01 as sub strings , but since they are not the complete strings, they are rejected. That's the demand of the question. Although, there's a problem of clarity in the statement. The fact that it has not to be a sub string could have been stated better. L = {Accepts the string 01 or a string of at least one 1 ended by exactly one 0.} This could have been a more clear representation of the DFA.

[@Thatefootballplayer]

Sahi bolla bhai tum

[@lucifer3646]

perfecto!

[@fenitagracebijoy4672]

Thanks for this.I was having the same doubt

[@mohammadvasimbaig8680]

00:09 Determining what the given DFA recognizes 01:33 Two types of strings are accepted 03:00 The DFA recognizes the string 0 1 or a string with at least one binary digit 1 followed by a 0. 04:35 Deterministic Finite Automata (DFA) accepts strings of at least 1 binary digit 1 followed by a 0. 05:59 The DFA does not have a place to go for certain inputs 07:16 Dead state is a state in a DFA that leads to non-accepted strings. 08:29 Implementing a DFA 09:53 Not having a terminating state in a DFA leads to a dead state Crafted by Merlin AI.

[@IndieDeveloperGuy]

So what this DFA does is : 1) Accepts 01 2) Accepts all strings that starts with 1 and ends with 0

[@usamabinmuzaffar692]

Your second point is wrong. It is supposed to be "Accepts all strings that have at least one '1' and end with '0'". The reason for this is that if you get a '0' after you are in state B, you will go to the terminating state D. After that, the string must be finished otherwise you go to the dead state X, as shown in the completed DFA. Be careful with these DFAs, they are extremely tricky and very easy to get wrong.

[@iulianalexandrudragan5531]

@@usamabinmuzaffar692 no, you're wrong, if it doesn't start with a 1 it goes on the other branch

[@yuanzhenggay799]

Thank you so much sir..... You saved my life

[@mayureshwadgaonkar2265]

Why haven't we applied a self loop for c if it's gets input 0..like we did for b for input 1

[@jennconn8378]

My God. It helps me a lot thank ypu

[@20mymysf]

What a plot twist! The X-state is like the zombie of the states!!

[@anuragporwal9039]

For DFA ,at C there should be a input '0',this is NFA

[@Farahat1234]

On 21 you have your exam??

[@anuragporwal9039]

@@Farahat1234 yup

[@hectorg362]

I freaken love you and this channel for this content!

[@AliAhmed-gg1tz]

is gaandu ko kuch nahi aata. if you like this channel tum bhi gaandu ho

[@jonaandgoshkoarebored7865]

we too

[@星际小男孩]

It is so fun, thank you very much.

[@StudyArtist-pl2bn]

00:07 Determining the language recognized by a DFA 01:28 Deterministic Finite Automata in action 02:56 DFA recognizes 0 1 or a string with at least one 1 followed by 0 04:31 Illustrating the acceptance of binary strings by a DFA 05:53 DFA transition fails for certain input strings 07:13 Introduction to Dead State in DFA 08:24 Deterministic Finite Automata example 4 09:51 Not terminating state = dead state

[@ahmetkarakartal9563]

thank you so much

[@christiana.collamar8924]

I think the constructed DFA only accepts a subset of strings defined by the language, e.g. the string 010 is not accepted even though it should be since it's a string with at least one 1 followed by a 0. To make the DFA accept such strings, I think these transitions must be followed: δ(E, 1) = B δ(D, 1) = B δ(X, 1) = B

[@danishsharma496]

I think he ment , starting with atleast one lol

[@asmaa4721]

Thanks it's was helpful , but please can you explain other example about AND

[@oguzkaanbulut2374]

L should be { 01 or strings has zero only at last index} since state d has not a behaviour for inputs 0,1 to loop itself

[@gunashiva2760]

very good explanation nice sir ..

[@yashnarang637]

can you please explain me what this dfa recognizes?

[@shouvikdutta2825]

01 and string starts with 1 and ends with 0??

[@shawonmandal9553]

What about 11010 It contains 1 followed by 0 it should be accepted according to the logic... But on this DFA it will be rejected and end up in X.

[@SpeakSatvik]

why we created the trap state, why we not put it to the final state to stay their whenever any input comes?

[@abhinavs2484]

Or you can simply write = 1*0 for the DFA

[@deekshit_Shetty]

Thanks sir it helped me alot 😁

[@gabrielsales7402]

But '1100' should be accepted, as it has at least one '1' followed by a '0' right there in the middle. Also '11010' should be accepted, for the same reason (it has a 1 followed by a 0). So a better, more descriptive definition for the language should be "Accepts the string 01 or a string that starts with a 1, followed by any amount of 1, ending with only one 0." That was a big description, but it at least somehow covers it.

[@vishalkumarjha3368]

Yes, there's a problem of clarity in the statement. The fact that it has not to be a sub string could have been stated better. L = {Accepts the string 01 or a string of at least one 1 ended by exactly one 0.} This could have been a more clear representation of the DFA.

[@tusharmahajan-ng2ch]

you're right!

[@gabrielsales7402]

@@tusharmahajan-ng2ch thanks I’m always right

[@shambhwishikha4977]

I have a que sir.. 001,010 in examples are called DFA or not?

[@jyosthna3769]

They are DFA only..... but not accepted by machine ..bcz the string 001 is not there in our language L.

[@rohitippili3834]

Thanks sir

[@pruthvirajmhaske]

4:28 Sir, Can I also say that, This DFA accepts any string not having 2nd input as '0' ?

[@BlizZarDaSh]

'10' is accepted by this DFA and the second input is '0'. Watch it again.

[@gauravkandekar2574]

In other words , this DFA accepts strings which doesn't contain 2 consecutive 0's(00 ).

[@shivamzoting3613]

or more than one 0

[@PlRATE]

why not just loop the 0 on c and loop 0,1 on the final states?

[@ayushiagrawal3009]

This DFA is still in complete as path 0 from the state B is not mentioned for example if we have a string 1011 then we can go from A to B at 1 but from B at 0 where we will go, we will be going to the dead state from B at 0. Please do mention this🙏🙏🙏🙏

[@vishalkumarjha3368]

If we get 0 at B, we will move to D. It is clearly mentioned.

[@udbhavvikramsingh3449]

Why not D goes back to state B if input is 1 at D, doing this way also satisfies the LANGUAGE right????? Correct me if i am wrong.

[@vardhman2344]

you have made the start state an accepting state also but this also means that the dfa accepts epsilon as input. Am i right?can start state be an accepting state?

[@Learn2earn-M]

شكرا جدا🌷

[@shinigamiryuk4183]

my teacher plays your videos in lectures

[@debashishmishra9309]

Awesome Videos.❤ . . The employee to entrepreneur add has started to appear everywhere and it's irritating.

[@AliAhmed-gg1tz]

randi k bachay ko kuch nahi aata. fail kara dy ga

[@apporvaarya]

nice just few more to go: )

[@ZainAli-xw8es]

language should be " accept 0,1 or string start with 1 and end with 0."

[@rajeevdey_8894]

What happen if '1111' string goes?🙄 According to me it will not reach upto final state. Means it is not acceptable?

[@srinivasr1948]

it will not accept bro

[@sdfpcplay9392]

So this is how you make spaceships in games

[@yashnarang637]

i think this will only accept two digit string which contains differ digits means only (01,10) thats it .

[@sandeepsingh87]

Are dead states also known as hang states?

[@savaj4756]

1:49 DJ Khaled : another one and another one

[@Vinod_Pandey14]

4:31 I think we can also say that a string of 0, 1 of min length 2 which starts and ends with different digits.

[@tradermann]

7:04 - 'this DFA is not wrong' Yes it is. All DFAs have have transition FOR EVERY SYMBOL in the alphabet, FROM EVERY STATE. So before you drew that dead state, your DFA was wrong. Otherwise, nice video. :)

[@keshavtha]

if there is no state given for an output we assume that it is going to a dead state ,so he is not wrong in saying that the DFA was not wrong.

[@toxicsoul8147]

Can we put (0,1) loop in both D and E states?...then the dead state is not needed..

[@sriman8083]

Sir I think it is not a DFA because in this all states not covers all transitions

[@shantipriya4661]

A deterministic finite automata does not need a transition from every state for every symbol.it is DFA

[@RahulSahu-fy6mr]

Watch the video till the end. You will get to know the answer.

[@yashnarang637]

sir, what if in state c we get another 0?

[@manikandannishanthmuthukum5227]

It will lead to dead state bro.

[@neiljohn2637]

#7-Up

[@nilansh_07]

Sir at 8:36 why we are not using self loop here on D for 0 and 1 please answer

[@alexwilson8269]

Would this no longer be deterministic? C has an option for when there is a 1 inputted, but no option for when 0 is inputted?

[@alexwilson8269]

Never mind, I just needed to finish the whole video 😅

[@lokesh_pathak248]

this is an example of nfa too

[@-Mounika-lh1dw]

S it's not example for dfa i think soo Bcz for dfa it must have 2alphabets that means 0,1 for ever state right

[@Ankit-we8ym]

will you cover gate sllabus

[@muhammedshahbas8706]

'The dead may never die.' Sounds familiar 🏹⚔️🗡️

[@rns031]

L={either starting with 01 or ending with 10}

[@fayssalelansari8584]

before changing the map with "001" the last 01 should match ?

[@abdullahcevizli2395]

it says it accepts string 01. not substring 01

[@unReaLDivyanshu]

X is like in Loki S1 void where everythigh is sent

[@Ankit-we8ym]

sir I am following TOC lectures they are very gud,do you teach any other sub of cse

[@continnum_radhe-radhe]

❤❤❤

[@tshepomatshisevhe4656]

Does this mean State C in the previous video can have many a's and end up having something like aaaaaab then it goes to state D? That means the string won't be accepted.

[@ayushsinghchauhan4121]

according to me, the ones he has taken besides the aabb must go to empty state... correct me if i m wrong and also suggest a example video for DFA...

[@bikoteedesigns]

Please can there be tutorial on how to draw a DFA to recognize source program?

[@harshananayakkara4854]

Once you are dead you stay dead 😁 Great explanations and video series 🙏

[@omkarb9866]

The Strings From Final State Will Never Be Transferred Or Accepted In Dead State.

[@infinity3016]

Is this not an NFA? Or at least an incomplete DFA. Edit: Oh he explained this but that’s so weird to start with an incomplete dfa

[@rahuldhindhwal9964]

nice one

[@lavanyadamarla4054]

What if b state doesn't get input 0 is the string can be accepted?

[@nuctanKatira]

why has c has only one 1 string ? why dont have 0 output?

[@sudiptacoachingcentre4118]

Sir why c don't have self loop

[@daviswang7104]

Actually this DFA doesn't represent at least '1' followed by a '0', if so, the string '010' wouldn't fail to the dead state, in fact, it represent a string start by '1', ended by '0', at the same time, whose content be filled with 0 to Inf numbers of '1'.

[@ziliestarrive]

You mean ONE 0 and any number of 1 greater or equal to one right? Otherwise you could have something like 11010 but then it goes to dead state.

[@vishalkumarjha3368]

Yes, there's a problem of clarity in the statement. The fact that it has not to be a sub string could have been stated better. L = {Accepts the string 01 or a string of at least one 1 ended by exactly one 0.} This could have been a more clear representation of the DFA.

[@codelikeapro9724]

if 1001 then b also should send 0 in dead state am i right??

[@KickassCoders]

sir what it's mean, 0 is divided by 5 and 1 is divided by 3

[@saranshkhurana7784]

Desi Coders man that question ruined me!

[@saranshkhurana7784]

i had that in an exam

[@Er.meghajain]

woow too good 👌

[@manavmalhotra8513]

what if the state 'C' gets 0?

[@amitshaw8788]

it will get trapped.

[@LethalChicken77]

Bad video, every state needs defined transitions for all symbols in the alphabet

[@emimini1737]

Hi sir, When the input is 1 in D what about sending back to B.Still the condition keep right?

[@RishikavsAnnie]

At first, I thought you were right, but no, if that happens, the string will have more 0's in between (Like 11010 or 101010) and I think that will not be accepted. They only want one 0, at the end. Lol, why am I answering this, you posted this a year ago, you're probably done with your exams for this subject. Hopefully, this will help someone else, though.

[@shivamchhabra7135]

@@RishikavsAnnie haha 😃😃 , so nice of you

[@rapidgamingzones]

@@RishikavsAnnie

[@sahinislam1163]

Is this also work for 101?

[@shreeyadhole5755]

Why is it so that when C gets input 0 it goes to dead state why it does not remian in itself.. like state B

[@lavanyadamarla4054]

Can I have a dead state in dfa

[@aayushm9377]

The string 010 contains atleast one '1' and is followed by a zero , it should be accepted but it goes to dead state?

[@sujithneelakandankizhakill9222]

I believe the confusion is with the language. The language could be modified to {01, or string starts with one and ends with 0, which should be the only 0 in the string}

[@vishalkumarjha3368]

Here, the string 1111....10 (at least one 1 followed by 0 is not assumed to be a sub string, it just is at least one 1 followed by one 0. ) For instance, 1110 will be accepted . But 11101 or 11100 will be rejected. So, stage D has to transition to Stage X to ensure rejection of the above mentioned strings. If stage D transitions to D itself, then 11101 and 11100 will both be accepted . If the case was that at least one 1 followed by a 0 was a sub-string(for example 11100 or 11101) then D should have transitioned to itself on 0 and 1 . The question is not about 01 or 111...10 being sub-strings . It either exactly has to be 01 or 111.....10 (n number of 1s followed by a 0, where n=1,2,3....). So, basically 1110 accepted. 11101 rejected. 11100 rejected. 01 accepted. 010 rejected. 010101 rejected . As we can see, the examples which have been rejected above have 1110 and 01 as sub strings , but since they are not the complete strings, they are rejected. That's the demand of the question.

[@vishalkumarjha3368]

Although, there's a problem of clarity in the statement. The fact that it has not to be a sub string could have been stated better. L = {Accepts the string 01 or a string of at least one 1 ended by exactly one 0.} This could have been a more clear representation of the DFA.

[@rutujadamkondwar]

can there be more than 1 dead state??

[@HarshitPubg]

Where is mod based question??

[@ChAkIrLbR]

is the dead state a must ?

[@pcv910]

Yes

[@24_nirmalodedara96]

sir if state have not transition edge to go othew state for any input it is not DFA ?? this is true ??

[@st529]

How can we get slides?

[@meliketekin5087]

nice

[@akash.manna.]

How can it be DFA? Isn't it NFA?

[@nishanttiwari9736]

is that diagram really a dfa????

[@vamshikrishnam9206]

what is the use of dead state y we are mentioning it. we can complete dfa without dead state

[@pcv910]

Every state must contain transition. Here for D,E has no transitions. And for C don't have 0 transition. So we used dead state.. And dead state also must have transition, so used self loop..

[@kedarsambhus3623]

Isn't this DFA incomplete? State C doesn't have a transition for input 0 and states D and E don't have any transitions.

[@mohshahud]

idiot

[@donglequang2248]

hi teacher, 001, if no X is predicted?

[@akshattrivedi2137]

It's not even a DFA yet , you've not defined the transitions over the final states and also a lot of other transitions. And we can only call a FSM a DFA when on all the states have all the transitions defined.

[@Asma-il3uh]

Yeah!! It's not deterministic. I was looking for this comment.

[@challengefitness-gz9bo]

India ko hindi sikhne ki jurt hai

[@shamegamesgametime1839]

It is not accepting 00

[@ranitbarman6471]

Who's downvoting these?????