Deterministic Finite Automata (Example 4)
ฝัง
- เผยแพร่เมื่อ 25 ส.ค. 2024
- TOC: An Example showing how to figure out what a DFA recognizes. This lecture shows how to figure out what a DFA recognizes and how to complete a DFA using a Dead State.
Full Course on TOC: goo.gl/f4CmJw
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Follow me on Instagram: @jaiz_itech (bit.ly/2M3xyOa)
Contribute: www.nesoacademy...
Memberships: bit.ly/2U7YSPI
Books: www.nesoacademy...
Website ► www.nesoacademy...
Forum ► forum.nesoacad...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#TheoryOfComputation #TOCByNeso #DeterministicFiniteAutomata #DFA #AutomataTheory
![[TH] 2024 PMSL SEA W2D5 | Fall | พลาดวันนี้ จะต้องเสียใจ](http://i.ytimg.com/vi/A5-Cuo12p6A/mqdefault.jpg)
'whatever happens in dead state , stays in dead state.' sounds familiar.
I was writing same and saw your comment.
'Whatever happens in Green mile, stays in green mile.'
@@sarthakpatel107 or area 52
People who ghost others do be like that
Vegas
This channel is really beautiful and very useful , thank's for your effforts
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.
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 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....).
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.
@@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"
@@vipuljha1818 Neither 1010 nor 010 are accepted due to going to the dead state
FAbulous way of teaching
mesmerizing indeed
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
well that's incorrect
@@omarmarnissi1458 why ?
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.
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.
i think it accepts only 01 and 1 followed by 0.
The 1 followed by 0 must be at the beginning of the string, so 010 is not accepted.
"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"
yeh bharwa fail karady ga tumhen
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.
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.
Thank you for the remark. I thought the state should be UNDEFINED, but your comment corrected my misconception.
it is corrected by adding a dead state in the second half of the video
@@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
He knows. Don't worry. That's why you should look the whole video before commenting.
@Neha Tadam firstly watch complete video then only come to a conclusion
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.
it doesnt have to start with 1
L={01, 1*0}
What a plot twist! The X-state is like the zombie of the states!!
So what this DFA does is :
1) Accepts 01
2) Accepts all strings that starts with 1 and ends with 0
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.
@@usamabinmuzaffar692 no, you're wrong, if it doesn't start with a 1 it goes on the other branch
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.
I have the same question as you.
@@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.
@@vishalkumarjha3368 thanks for the explanation.
It is so fun, thank you very much.
Why haven't we applied a self loop for c if it's gets input 0..like we did for b for input 1
My God. It helps me a lot thank ypu
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.
Sahi bolla bhai tum
perfecto!
Thanks for this.I was having the same doubt
Thank you so much sir..... You saved my life
I freaken love you and this channel for this content!
is gaandu ko kuch nahi aata. if you like this channel tum bhi gaandu ho
we too
Thankyou sir
01 and string starts with 1 and ends with 0??
What happen if '1111' string goes?🙄
According to me it will not reach upto final state. Means it is not acceptable?
it will not accept bro
nice just few more to go: )
thank you so much
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.
Thank you
For DFA ,at C there should be a input '0',this is NFA
On 21 you have your exam??
@@Farahat1234 yup
X is like in Loki S1 void where everythigh is sent
Thanks sir it helped me alot 😁
So this is how you make spaceships in games
very good explanation nice sir ..
can you please explain me what this dfa recognizes?
Sir I think it is not a DFA because in this all states not covers all transitions
A deterministic finite automata does not need a transition from every state for every symbol.it is DFA
Watch the video till the end. You will get to know the answer.
Thanks sir
Thanks it's was helpful , but please can you explain other example about AND
why not just loop the 0 on c and loop 0,1 on the final states?
I have a que sir.. 001,010 in examples are called DFA or not?
They are DFA only..... but not accepted by machine ..bcz the string 001 is not there in our language L.
sir, what if in state c we get another 0?
It will lead to dead state bro.
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?
my teacher plays your videos in lectures
شكرا جدا🌷
'The dead may never die.' Sounds familiar 🏹⚔️🗡️
4:28 Sir, Can I also say that, This DFA accepts any string not having 2nd input as '0' ?
'10' is accepted by this DFA and the second input is '0'. Watch it again.
language should be " accept 0,1 or string start with 1 and end with 0."
why we created the trap state, why we not put it to the final state to stay their whenever any input comes?
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
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.
Once you are dead you stay dead 😁 Great explanations and video series 🙏
Or you can simply write = 1*0 for the DFA
what if the state 'C' gets 0?
it will get trapped.
Sir why c don't have self loop
woow too good 👌
#7-Up
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.
Are dead states also known as hang states?
this is an example of nfa too
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
Sir at 8:36 why we are not using self loop here on D for 0 and 1 please answer
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
I think he ment , starting with atleast one lol
nice one
Can we put (0,1) loop in both D and E states?...then the dead state is not needed..
Is this also work for 101?
What if b state doesn't get input 0 is the string can be accepted?
In other words , this DFA accepts strings which doesn't contain 2 consecutive 0's(00 ).
or more than one 0
why has c has only one 1 string ? why dont have 0 output?
i think this will only accept two digit string which contains differ digits means only (01,10) thats it .
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
sir if state have not transition edge to go othew state for any input it is not DFA ?? this is true ??
if 1001 then b also should send 0 in dead state am i right??
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🙏🙏🙏🙏
If we get 0 at B, we will move to D. It is clearly mentioned.
Can I have a dead state in dfa
starting eg. is not a dfa look at c state why are u considering dfa sir please tell me
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.
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. :)
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.
nice
before changing the map with "001" the last 01 should match ?
it says it accepts string 01. not substring 01
Where is mod based question??
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?
Never mind, I just needed to finish the whole video 😅
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.
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.
you're right!
@@tusharmahajan-ng2ch thanks I’m always right
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.
Yeah!!
It's not deterministic.
I was looking for this comment.
How can it be DFA? Isn't it NFA?
will you cover gate sllabus
ups...
Awesome Videos.❤
.
.
The employee to entrepreneur add has started to appear everywhere and it's irritating.
randi k bachay ko kuch nahi aata. fail kara dy ga
can there be more than 1 dead state??
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
How can we get slides?
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.
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...
hi teacher,
001, if no X is predicted?
what is the use of dead state y we are mentioning it.
we can complete dfa without dead state
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..
Please can there be tutorial on how to draw a DFA to recognize source program?
The string 010 contains atleast one '1' and is followed by a zero , it should be accepted but it goes to dead state?
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}
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.
how can B store so many instances of '1' as said by you that DFA's have very low memory?
I doesn't store any instances. All state B knows is "input string started with '1' and no '0' has appeared yet".
Hi sir, When the input is 1 in D what about sending back to B.Still the condition keep right?
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.
@@RishikavsAnnie haha 😃😃 , so nice of you
@@RishikavsAnnie
#Excelent!
The Strings From Final State Will Never Be Transferred Or Accepted In Dead State.
L={either starting with 01 or ending with 10}
Sir what about string (11010 ) here also 1 followed by 0 but it is in dead state. why?
S .
Yeah, that's what I'm thinking. I guess the language definition is off. We could try to come up with a better definition for this state machine. Maybe something like "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 covers it.
@@gabrielsales7402 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.
sir what it's mean, 0 is divided by 5 and 1 is divided by 3
Desi Coders man that question ruined me!
i had that in an exam
❤❤❤
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.
idiot
is the dead state a must ?
Yes
is that diagram really a dfa????
It is not accepting 00