@@himanshu6489 Neso's teaching is better than any top level USA professors who teach automata. God, I can't believe automata can be learned in Neso's way.
Great videos! Thank you for going through each step in such detail, it really helps to trace the line of thought necessary to solve these problems. Much appreciated.
You guys are besttttttttttt thank you so much I am trying to solve this one for so long but because of some miscalculations I was not able to get it thankkkk youuuu
No , {q0 , q4 , q6} will be in same set q0 and q6 are 1 equivalence because , (q0 on getting '0' goes to q1) && (q6 on getting 0 goes to q6) ->(different states but ,q1 ,q6 are in same set ) Similarly (q0 on getting '1' goes to q5 ) && (q6 on getting 1 goes to q4 ) ->(Here also diff states , but q5 , q4 are in same set) Therefore q0 and q6 are 1 equivalence. So {q0 , q4 , q6 } will be in same set in 1 equivalence. Also try checking (q6 with q4 you will understand).
if you are commenting such a way then you should let the viewers knows which states are you exactly talking about?You made a comment now every one confused whome already where lmao: p
sir, we always have to remove the states that is not reachable from initial state. This transition table has one not reachable state. If we don't remove we may not get minimized DFA. You can try with example.
@@Patrick-hb9dbj unreachable means, unreachable from the initial state, ie, q0. Any string (continuous series of input values) will not end in Q3 , ie, it's unreachable. Your deduction, too, is correct but sometimes a state is given on the right side of table( columns of 0 and 1) , yet still unreachable.
q3 and q5 are not 3 equivalence of each other, q3->0->q2 q3->1->q6 q5->0->q2 q5->1->q0. In 2 equivalence q0 and q6 are not in the same group hence, q3 and q5 can not be in the same group in 3 equivalence. So, 3 equivalence should be {q0, q4} {q6} {q1, q7} {q3} {q5} {q2}.
In the 3-equivalent the set(q3, q5) are not three equivalent in myside, I am confusing to solve three equivalent now help to clearify of this problem.. No doubt you are a great teacher and great academy..
I think q1 and q7 should be placed in separate groups as while getting 3equivalence they come give output in different group with input 0. Please clarify!
Both q1 and q7 have q6 when the input is 0, and q6 belongs in a group with only 1 member(i.e. q6). So they both have q6 and so, both of their inputs belong to the SAME group, i.e. the one which contains q6. That's all that matters here
in 2 equivalence,when checking for q0 and q4,on getting input 0 states donot belong to the same set.then how can{q0,q4} be in the same set in 3 equvalence?
q3 is unreachable from initial state . q3 never appears at the right side of the vertical line , means no any state which is reachable will lead us to q3 Any way answer is same . Nice video, Thanks
at 5:00 , why wont q1 and q2 be equivalent ? Since boths outputs are respectively in same sets. Is the reason because q1 and q2 were in different sets in the above row ?
can i write like this in my exam like mentioning 0 equivalence 1 equivalence and so on, do u think that i can get marks by writing like this or i have to mention everything step by step?? plz reply
No because for 0 (q3,q5) goes for same set, and for 1(q3,q5) goes to the same set. From what I understood, it seems like the Individual values (0,1) in both states q3,q5 should be part of "a" same set and it's not necessary for both 1 and 0 to be together in a set. 0 1 q3 q2 q6 q5 q2 q6 ^ ^ {q2} {q6}
I have a doubt, in 2-equivalence, q0 and q4 should be in two different sets because q1 and q7 belong to same set but q5 belongs to a different set. so q1, q7 and q5 together are not in the same set. Someone please clear this doubt. thanks
for 0 q0 goes to 'q1' and q4 goes 'q7' which are in the same set and for 1 q0 goes to 'q5' and q4 also goes to 'q5' they are also in same state so they are 2 equivalent. I hope you understand or just watch the video from 1 equivalence you will understand what I'm talking
Please reply! I have first solved it then saw your solution Mine and yours answer is same but slight difference is that I have not considered q3 because q3 is unreachable state
how does {q0 and q4} are in same state in 2nd equivalence even though on comparing both q0 &q4 on 0 input it gives q1 and q7 and on input 1 its q5. now, if we check it in 1st equivalence there's no q1,q7 and neither q5 as well these state are not present in same state in 1st equivalence.As combination is {q0,q4,q6} so it became equivalent(i.e {q0,q4}). guyz plz if any one can figure out this plz reply to this comment ASAP
It's a mistake in equivalence 1 when you compare q0 with q4 when you compare with 0 it's shows q1 and q7 how ever q1 is no longer in same set so q4 will be separate set
{q3,q5 } q3 on 0 goes to q2 , on 1 goes to q6 q5 on 0 goes to q2, on 1 goes to q6 Here q2 and q6 belong to different set so they should not be kept together. 4:18 Correct me if I Missed something
can ya explain how in one equivalence q6 is with {q0, q4}. after matching nothing is coming common b/w them therefore do not we have to make another new state for it ? please answer asap
The video is correct. q6 is equivalent to q4 because upon receiving input '0' q6->q6 and q4->q7. q6 and q7 are in the same set in 0 equivalence. Upon receiving input '1' q6->q4 and q4->q5. q4 and q7 are in the same set in 0 equivalence. Therefore, q0, q4, and q6 are equivalent. q6 is not equivalent to q7 because upon receiving input '1' q6->q4 and q7->q2. q4 and q2 are not in the same set in 0 equivalence. Therefore, q6 is not equivalent to q7.
Navdeep In 0 equivalence, you have to distribute FS(Final State) and IS(Intermadiate state) in 2 different set. Now in 1st equivalence,we have to check whether the output of a 2 states at a particular input falls at the same set that we saw in 0 equ. Here, q0 q4 q6 has outputs: q1 q7 q6 on input 0 q5 q5 q4 on input 1 where , q1 q4 q5 q6 q7 falls in same set that we had on equivalence 0.
Sir , in this Examplef the q3 is Unreachable state, then why you considered it, From initial state we can't reach to the q3 state. Sir please reply ASAP , I have examination. ❤
Sir in example-1 you have taken union in transition table and in example-2 you doing different thing. And we are taking union in example-2 different table in formed...
Neso Academy is not only a channel. It is an emotion to me
Bro emotion for me hota hai😊
Better than my professor. Thanks for the clear explanation! and the way you say equivalent!!!! Like butter
you're from which country?
@@himanshu6489 Neso's teaching is better than any top level USA professors who teach automata. God, I can't believe automata can be learned in Neso's way.
better than any college professor
@@marxman1010neso is run by Indian
Same 😢
this is helping me before midterm exam..........
Same ❤️
bruh sem :'3
Same 2 me also
I'm doin its midterm in 1 hour :( :)
@@mohamedmansour6177I have exam at 13.30 . how was your exam?
You have saved me from Backlog in Automation Hatsoff sir to you much love !!
thank you this video helps me to understand easily the concept of DFA minimization. Neso is best
Great videos! Thank you for going through each step in such detail, it really helps to trace the line of thought necessary to solve these problems. Much appreciated.
You guys are besttttttttttt thank you so much I am trying to solve this one for so long but because of some miscalculations I was not able to get it thankkkk youuuu
q3 is unreachable state. Before forming equivalence class, you must remove q3.
Ya we have to remove Q3 before any operation
In 4:45 how q6 became with {q0,q4} aren’t they went to different sets with input 1 ?
i was confused too, but q0(0) and q6(0) lies in one 0-equivalent set
4:45 in 1 equivalent q6 not equivalent with q0 and q4...
Thanks for amazing explaination 🤩
Thanks for the correction
exactly in 1 equivalence q6 is a part of {q1,q7,q6}
No , {q0 , q4 , q6} will be in same set
q0 and q6 are 1 equivalence
because ,
(q0 on getting '0' goes to q1) && (q6 on getting 0 goes to q6) ->(different states but ,q1 ,q6 are in same set )
Similarly
(q0 on getting '1' goes to q5 ) && (q6 on getting 1 goes to q4 ) ->(Here also diff states , but q5 , q4 are in same set)
Therefore q0 and q6 are 1 equivalence. So {q0 , q4 , q6 } will be in same set in 1 equivalence. Also try checking (q6 with q4 you will understand).
In minimization of DFA first we have to remove unreachable state, that you haven't done in this question.
if you are commenting such a way then you should let the viewers knows which states are you exactly talking about?You made a comment now every one confused whome already where lmao: p
@@programmer6953 if you can't tell which state is unreachable then there is no point for you to watch this video
@@mranonymous9126 how about q3 mr computer scientist
@@comfycat7425 sorry mate my bad
@@comfycat7425 i think q3 is unreachable
4:48 how is q6 equivalent to q0 and q4. It doesn't seem to be true.
Someone Give this man a medal✌
Literally this video is helping me before the sem exam.....😌
mid term me mere 89 out of 100 aaye hai thanx neso academy sirf aapki vajah se possible ho paya ye thanx neso academy
sir, we always have to remove the states that is not reachable from initial state. This transition table has one not reachable state. If we don't remove we may not get minimized DFA. You can try with example.
q3 is unreachable.
yeah, solved problem is wrong
Yes q3 is not reachable
how did you identify q3 is not reachable?
as q3 is missing in 0 and 1 column hence you concluded, right?
@@Patrick-hb9dbj unreachable means, unreachable from the initial state, ie, q0.
Any string (continuous series of input values) will not end in Q3 , ie, it's unreachable.
Your deduction, too, is correct but sometimes a state is given on the right side of table( columns of 0 and 1) , yet still unreachable.
q3 and q5 are not 3 equivalence of each other,
q3->0->q2
q3->1->q6
q5->0->q2
q5->1->q0.
In 2 equivalence q0 and q6 are not in the same group hence, q3 and q5 can not be in the same group in 3 equivalence.
So, 3 equivalence should be {q0, q4} {q6} {q1, q7} {q3} {q5} {q2}.
1 equivalence is not correct. q0,q4 are one set, q1,q6,q7 are one set. from there the mistake started
10:37 , sir you wrote q2 will go to q0 and q4 which is wrong as it will only go to q0 with input 0. Please correct it.
yh I think you are right.
Thank you this helped me so much more than the stuff that my professor gave me
Here q3 is the unreachable state so we will discard that state. Please clarify sir.
watch previous videos....
Yes you are right. The correct answer is:
{0, 4} {6} {1, 7} {4} {2}
how is q3 unreachable
@@anonymoussloth6687 affects nothing buddy, you have five states this solution has 5 states,they both are the same!
This is so soo helpful for midterm examination
In the 3-equivalent the set(q3, q5) are not three equivalent in myside, I am confusing to solve three equivalent now help to clearify of this problem..
No doubt you are a great teacher and great academy..
That's clear buddy, silly mistake by sir.
In 3-equivalent Q3 and Q5 are in the different set .
@@AnishKumar-wh9qy they are in same set, are'nt they ? (7:49)
Yes you are correct
@@AnishKumar-wh9qy no they are in same equivalence. they both have q2 and q6 for 0 and 1
no they are in same equivalence. they both have q2 and q6 for 0 and 1
At 2 Equivalence q0 and q6 are in defferent State .
so how in 3 Equivalence q3 and q5 are in same State??????
@Harshal Patil so that was q6 and not q0?
@@stoneshot6062 exactly
Too clear sir.... thankyou
Thank you for realy good and detail explanation
I think q1 and q7 should be placed in separate groups as while getting 3equivalence they come give output in different group with input 0. Please clarify!
Yes ... You are right . With input 0 and input 1 as well
i agree, i think there's little mistake
Both q1 and q7 have q6 when the input is 0, and q6 belongs in a group with only 1 member(i.e. q6). So they both have q6 and so, both of their inputs belong to the SAME group, i.e. the one which contains q6. That's all that matters here
Please dont make us more confuse, we are already confused a lot.
they transit to the same location for both 0 and 1. Hence ofc they should be in the same group.
Thank you so much Sir your videos are really helpful Sir.
if q2 is already a disjoint set then why compared q3 with q2 and joined them ??
while making the final transition table for minimized DFA can we write like {q1, q2} instead of q1q2? doesnt that make it NFA?
1 equivalence is not correct. q0,q4 are one set, q1,q6,q7 are one set. from there the mistake started
The video is well explaining, i really like your tutorial. Big up men
in 2 equivalence,when checking for q0 and q4,on getting input 0 states donot belong to the same set.then how can{q0,q4} be in the same set in 3 equvalence?
I was just wondering the same thing
Superb explanation Sir!
Really helps a lot ur videos thank you so very much !!!!
Bro tu pan ithech lol
Tq so much sir very effective and clear explanation..
q3 is unreachable from initial state . q3 never appears at the right side of the vertical line , means no any state which is reachable will lead us to q3
Any way answer is same . Nice video, Thanks
It's fun to learn with you !
in 1 equivalence, how q6 is equivalent to q0 or q4?
same doubt
I think he must've made a mistake. I've been redoing it trying to figure out how he did it and I can't find a solution. He must've made a mistake.
Sir u really explain so we'll tqq 😍😍
Great explanation❤
Thanks man love from india
Amazing video!! You explain it really good!!
at 5:00 , why wont q1 and q2 be equivalent ? Since boths outputs are respectively in same sets.
Is the reason because q1 and q2 were in different sets in the above row ?
Bot q2 is final state it can't be equivalent
Amazing content. Thanks a lot Neso.
Your video is very clear with clear
Listening to this guy makes me feel so safe... Everything is explainable, everything is gonna be okay, don't worry 🥲
Thank you so much for clearing the concept
is equivalence-3 saturates Q3 and Q5,?
NO
can i write like this in my exam like mentioning 0 equivalence 1 equivalence and so on, do u think that i can get marks by writing like this or i have to mention everything step by step?? plz reply
I think q3 and q5 will be separate in 3.equivalence.
Yes ,
Noo q1 and q7 will be separated
no.. never because for 0 as well as for 1 input they are going to the same state . so they are totally equivallnce
No because for 0 (q3,q5) goes for same set, and for 1(q3,q5) goes to the same set. From what I understood, it seems like the Individual values (0,1) in both states q3,q5 should be part of "a" same set and it's not necessary for both 1 and 0 to be together in a set.
0 1
q3 q2 q6
q5 q2 q6
^ ^
{q2} {q6}
I have a doubt, in 2-equivalence, q0 and q4 should be in two different sets because q1 and q7 belong to same set but q5 belongs to a different set. so q1, q7 and q5 together are not in the same set.
Someone please clear this doubt. thanks
for 0 q0 goes to 'q1' and q4 goes 'q7' which are in the same set and for 1 q0 goes to 'q5' and q4 also goes to 'q5' they are also in same state so they are 2 equivalent. I hope you understand or just watch the video from 1 equivalence you will understand what I'm talking
Awesome exponation. At last it clicked to me, lol.
You probably forgot to combine the states in the transition table, this was DFA .. so it could not have multiple states ... see 10:50
it is not multiple state, state name is {q1, q7}
excellent explanation
Yolu save my life .respect from turkey Comp.engineering department
in the transition table at the end {q0, q4} -> for 1 should be {q5} only.
correct me if I'm wrong.
same doubt
Hey guys don't we remove unreachable states first before making equivalences?
Please reply!
I have first solved it then saw your solution Mine and yours answer is same but slight difference is that I have not considered q3 because q3 is unreachable state
Sir in the last of this video in the transition table for minimized DFA ...y does q2 will get {q0,q4} for the zero input ?it should be q0 itself ryt?
friend for 1 is q2 itself and for 0 the two equivalent states q0q4
@@yummycandy1703 How it can be q0q4 for q2 ?
Tq sir now I'm getting clear about this topic
how does {q0 and q4} are in same state in 2nd equivalence even though on comparing both q0 &q4 on 0 input it gives q1 and q7 and on input 1 its q5. now, if we check it in 1st equivalence there's no q1,q7 and neither q5 as well these state are not present in same state in 1st equivalence.As combination is {q0,q4,q6} so it became equivalent(i.e {q0,q4}). guyz plz if any one can figure out this plz reply to this comment ASAP
same problem I have, please if you know the solution, please tell me
very clear explanation....thank godd..!! and you sir!!
Thankyou !!
Sir, does we need to construct a DFA state diagram at the end?
For minimization of dfa first we have to remove unreachable state right?
Sir how q6 will group with q0
It will group with q1 4:45
I have some doubt…in what order we have to pick elements from Non-Final states list?
Ur excellent bro ....
It's a mistake in equivalence 1 when you compare q0 with q4 when you compare with 0 it's shows q1 and q7 how ever q1 is no longer in same set so q4 will be separate set
You are right
for doing q0 and q4 the q5 lies in different set right?
Yes that's what I'm confused abt
q3 is an unreachable state and must have been removed from the table even before we check equivalence right?
Yeah i was thinking the same
what if there is more than 1 final state? do I have to check if it is equivalance or not?
How do you know that q2 is an exit state? How did you figure it out?
can anybody explain the q6 in the 1st equivalence....i think it is wrong the steps that he skipped? if i'm wrong please help me to reach out...!
Sir how q6 is equal to q0 q4
Thats a mistake , also q0 q7 wont be equal to q3 q5 but only q5
There is no mistake please watch video with focus
Are you dumb 😅
q3 is unreachable state so it should be eliminated right?
great video
Thank u. Good explanation
Excellent sir.
q3 and q5 should be separate in equivalence of 3
{q3,q5 }
q3 on 0 goes to q2 , on 1 goes to q6
q5 on 0 goes to q2, on 1 goes to q6
Here q2 and q6 belong to different set so they should not be kept together.
4:18
Correct me if I Missed something
Sir you did a mistake at one equivalence as {q3,q5} should not fall in same set ,since they are going to final state
15minutes before exam just enough time to watch the video 🤣🤣
can ya explain how in one equivalence q6 is with {q0, q4}. after matching nothing is coming common b/w them therefore do not we have to make another new state for it ? please answer asap
Yeah dunno either. Think he might've made a mistake. Should be with {q1,q7}
The video is correct.
q6 is equivalent to q4 because upon receiving input '0' q6->q6 and q4->q7. q6 and q7 are in the same set in 0 equivalence. Upon receiving input '1' q6->q4 and q4->q5. q4 and q7 are in the same set in 0 equivalence. Therefore, q0, q4, and q6 are equivalent.
q6 is not equivalent to q7 because upon receiving input '1' q6->q4 and
q7->q2. q4 and q2 are not in the same set in 0 equivalence. Therefore, q6 is not equivalent to q7.
Navdeep In 0 equivalence, you have to distribute FS(Final State) and IS(Intermadiate state) in 2 different set.
Now in 1st equivalence,we have to check whether the output of a 2 states at a particular input falls at the same set that we saw in 0 equ.
Here, q0 q4 q6 has outputs:
q1 q7 q6 on input 0
q5 q5 q4 on input 1
where , q1 q4 q5 q6 q7 falls in same set that we had on equivalence 0.
why q2X0={q0,q4 }? at 10:31
Great explanation! At first I thought you were doing it wrong, my bad :(
please why did q2 get the states {q0,q4} can someone explain to me please.
how does the q6 is 1 equivalent to q0 and q4?
How qo and q4 are equal, there input is in different set right
q3 is unreachable so can we remove it in initial stage only?
YES THIS ONE..
what is the regular expresion for this DFA?
Why didn't you remove the unreachable state first, i.e, q3 ???
Why is that unreachable?
I still don't get it. In 1 equivalent how q0,q4, but how q6 is in the same state?
Sir , in this Examplef the q3 is Unreachable state, then why you considered it,
From initial state we can't reach to the q3 state.
Sir please reply ASAP , I have examination.
❤
I have a doubt what if one of the states on giving an input directs to a dead state.What to do then.
Look at the title, it is conversion of DFA
What's the logic behind this method of checking equivalence using previous set
i didnt get it in the second equivalence
yeah i too think its wrong in q2
Sir q6 and q7 ka 1 equivalence kya hoga
Rply me urgently
Both states will place in different sets
I'm curious, what is the Lm of this DFA?
Sir in example-1 you have taken union in transition table and in example-2 you doing different thing.
And we are taking union in example-2 different table in formed...
This come in my final exam
Answer should be {q0, q4} {q6} {q1, q7} {q3,q5} {q2}.