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.
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.
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.
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"
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
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.
@@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
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.
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 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.
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
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.
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.
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. :)
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
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?
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🙏🙏🙏🙏
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.
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.
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..
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.
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.
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.
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.
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.
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'.
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.
it needs to begin with 1, have consecutive undetermined 1's and then end with 0, so something like L1 = {Accepts string '01' or any string beginning with one or more '1' while ending with '0'}, is a more accurate Language for this example DFA
'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
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.
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.
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
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
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
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
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.
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.
Why haven't we applied a self loop for c if it's gets input 0..like we did for b for input 1
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}
Thank you so much sir..... You saved my life
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.
Sir at 8:36 why we are not using self loop here on D for 0 and 1 please answer
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
It is so fun, thank you very much.
My God. It helps me a lot thank ypu
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
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.
01 and string starts with 1 and ends with 0??
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.
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
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
For DFA ,at C there should be a input '0',this is NFA
On 21 you have your exam??
@@Farahat1234 yup
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
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?
sir, what if in state c we get another 0?
It will lead to dead state bro.
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.
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.
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.
What a plot twist! The X-state is like the zombie of the states!!
very good explanation nice sir ..
can you please explain me what this dfa recognizes?
Can we put (0,1) loop in both D and E states?...then the dead state is not needed..
What if b state doesn't get input 0 is the string can be accepted?
why we created the trap state, why we not put it to the final state to stay their whenever any input comes?
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?
Thanks sir it helped me alot 😁
sir if state have not transition edge to go othew state for any input it is not DFA ?? this is true ??
Are dead states also known as hang states?
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
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.
if 1001 then b also should send 0 in dead state am i right??
Is this also work for 101?
before changing the map with "001" the last 01 should match ?
it says it accepts string 01. not substring 01
Or you can simply write = 1*0 for the DFA
my teacher plays your videos in lectures
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
1:49 DJ Khaled : another one and another one
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..
Sir why c don't have self loop
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.
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.
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
why has c has only one 1 string ? why dont have 0 output?
thank you so much
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...
i think this will only accept two digit string which contains differ digits means only (01,10) thats it .
How can we get slides?
nice just few more to go: )
00110 is same as 110 but 1st one is houng to the dead state. Could anyone please explain
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.
can there be more than 1 dead state??
Once you are dead you stay dead 😁 Great explanations and video series 🙏
is the dead state a must ?
Yes
شكرا جدا🌷
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".
what if the state 'C' gets 0?
it will get trapped.
will you cover gate sllabus
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.
So this is how you make spaceships in games
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
Thanks sir
In other words , this DFA accepts strings which doesn't contain 2 consecutive 0's(00 ).
or more than one 0
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'.
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.
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.
hi teacher,
001, if no X is predicted?
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
so, basically this dfa accepts 01+{1*0} ??
I think so
no, the right answer is (01| 1^+ 0)
the number 1 should be (one or more => (+) ) not (zero or more => (*) )
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 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
Can I have a dead state in dfa
language should be " accept 0,1 or string start with 1 and end with 0."
'The dead may never die.' Sounds familiar 🏹⚔️🗡️
Please can there be tutorial on how to draw a DFA to recognize source program?
sir I am following TOC lectures they are very gud,do you teach any other sub of cse
Bad video, every state needs defined transitions for all symbols in the alphabet
woow too good 👌
How can it be DFA? Isn't it NFA?
is that diagram really a dfa????
Can't we say string 01 and string with atleast one 1 and ending with 0
it needs to begin with 1, have consecutive undetermined 1's and then end with 0, so something like L1 = {Accepts string '01' or any string beginning with one or more '1' while ending with '0'}, is a more accurate Language for this example DFA
L={either starting with 01 or ending with 10}
The Strings From Final State Will Never Be Transferred Or Accepted In Dead State.
6:14
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
Where is mod based question??
❤❤❤
X is like in Loki S1 void where everythigh is sent