Minimization of DFA (Example 2)

[@UjjwalRaj-CSE-]

Neso Academy is not only a channel. It is an emotion to me

[@devilgaming4869]

Bro emotion for me hota hai😊

[@TheImperialzero]

Better than my professor. Thanks for the clear explanation! and the way you say equivalent!!!! Like butter

[@himanshu6489]

you're from which country?

[@marxman1010]

@@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.

[@rikengaming5652]

better than any college professor

[@tailung6334]

​@@marxman1010neso is run by Indian

[@ssanyaverma]

Same 😢

[@ganjargingintahyudin9774]

this is helping me before midterm exam..........

[@henrycavil3385]

Same ❤️

[@tanmoy.mazumder]

bruh sem :'3

[@gopireddy9308]

Same 2 me also

[@mohamedmansour6177]

I'm doin its midterm in 1 hour :( :)

[@ahmetkarakartal9563]

@@mohamedmansour6177I have exam at 13.30 . how was your exam?

[@jatinchourasia8347]

You have saved me from Backlog in Automation Hatsoff sir to you much love !!

[@finder2023]

thank you this video helps me to understand easily the concept of DFA minimization. Neso is best

[@arunavaghosh4635]

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

[@bharath4713]

Someone Give this man a medal✌

[@phillipmichalowski]

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.

[@pycoder_official]

4:45 in 1 equivalent q6 not equivalent with q0 and q4... Thanks for amazing explaination 🤩

[@Nikhil-dp2mw]

Thanks for the correction

[@romitbhattacharya8172]

exactly in 1 equivalence q6 is a part of {q1,q7,q6}

[@ABDULSAMAD-u6r]

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).

[@aakashkurmi35]

@@ABDULSAMAD-u6r no

[@ashhmuds1173]

q3 is unreachable state. Before forming equivalence class, you must remove q3.

[@ratneshsingh8403]

Ya we have to remove Q3 before any operation

[@churakantiakshithareddy8936]

Literally this video is helping me before the sem exam.....😌

[@nitindiwakar_1857]

In minimization of DFA first we have to remove unreachable state, that you haven't done in this question.

[@programmer6953]

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

[@comfycat7425]

​@@programmer6953 if you can't tell which state is unreachable then there is no point for you to watch this video

[@comfycat7425]

@@mranonymous9126 how about q3 mr computer scientist

[@mranonymous9126]

@@comfycat7425 sorry mate my bad

[@aminatithi8781]

@@comfycat7425 i think q3 is unreachable

[@richamishra7107]

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.

[@sajalsingh7727]

q3 is unreachable.

[@abhi.2407]

yeah, solved problem is wrong

[@bhavnagohatiya7164]

Yes q3 is not reachable

[@Patrick-hb9dbj]

how did you identify q3 is not reachable? as q3 is missing in 0 and 1 column hence you concluded, right?

[@tanaygaur5033]

@@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.

[@wallcasey52]

Thank you this helped me so much more than the stuff that my professor gave me

[@gopireddy9308]

This is so soo helpful for midterm examination

[@gadhamshettyyamini8314]

Too clear sir.... thankyou

[@manasameria524]

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}.

[@kavyahegade6477]

1 equivalence is not correct. q0,q4 are one set, q1,q6,q7 are one set. from there the mistake started

[@creativeideas4170]

mid term me mere 89 out of 100 aaye hai thanx neso academy sirf aapki vajah se possible ho paya ye thanx neso academy

[@yaroslawliker]

Thank you for realy good and detail explanation

[@vrushaligholap6647]

Superb explanation Sir!

[@kandy5983]

In 4:45 how q6 became with {q0,q4} aren’t they went to different sets with input 1 ?

[@lan2562]

i was confused too, but q0(0) and q6(0) lies in one 0-equivalent set

[@itv5610]

4:48 how is q6 equivalent to q0 and q4. It doesn't seem to be true.

[@CharmingMoments09]

Thank you so much Sir your videos are really helpful Sir.

[@nawwalwaseer4691]

Great explanation❤

[@gideonmutiso9426]

The video is well explaining, i really like your tutorial. Big up men

[@kanchasaailaa7536]

if q2 is already a disjoint set then why compared q3 with q2 and joined them ??

[@viswanadhvarmakallepalli5148]

Here q3 is the unreachable state so we will discard that state. Please clarify sir.

[@Rahulsingh-bu6jh]

watch previous videos....

[@anonymoussloth6687]

Yes you are right. The correct answer is: {0, 4} {6} {1, 7} {4} {2}

[@yummycandy1703]

how is q3 unreachable

[@NotcoolNotcool]

@@anonymoussloth6687 affects nothing buddy, you have five states this solution has 5 states,they both are the same!

[@cool_guy_Vaibhav]

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.

[@Ogg_skimmer]

yh I think you are right.

[@ommule4999]

Really helps a lot ur videos thank you so very much !!!!

[@APURVSHEWALEBCE]

Bro tu pan ithech lol

[@nisha_editz3099]

Tq so much sir very effective and clear explanation..

[@srikanthtalks4877]

excellent explanation

[@knowledge_apna]

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..

[@AnishKumar-wh9qy]

That's clear buddy, silly mistake by sir. In 3-equivalent Q3 and Q5 are in the different set .

[@user-wl5nl3gb9p]

@@AnishKumar-wh9qy they are in same set, are'nt they ? (7:49)

[@ganeshreddykomitireddy5128]

Yes you are correct

[@kavyahegade6477]

@@AnishKumar-wh9qy no they are in same equivalence. they both have q2 and q6 for 0 and 1

[@kavyahegade6477]

no they are in same equivalence. they both have q2 and q6 for 0 and 1

[@lima073]

It's fun to learn with you !

[@vollyballMan]

At 2 Equivalence q0 and q6 are in defferent State . so how in 3 Equivalence q3 and q5 are in same State??????

[@stoneshot6062]

@Harshal Patil so that was q6 and not q0?

[@buzzbony1068]

@@stoneshot6062 exactly

[@rajatsaini7267]

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!

[@prateekrao6710]

Yes ... You are right . With input 0 and input 1 as well

[@ganjargingintahyudin9774]

i agree, i think there's little mistake

[@jagjot1697]

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

[@Farahat1234]

Please dont make us more confuse, we are already confused a lot.

[@adityadhal5027]

they transit to the same location for both 0 and 1. Hence ofc they should be in the same group.

[@Viscos2000]

Sir u really explain so we'll tqq 😍😍

[@AjeetKumar-mo6xt]

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

[@surajdubey5391]

Your video is very clear with clear

[@ananyadutta2490]

I think q3 and q5 will be separate in 3.equivalence.

[@loadingfuture9856]

Yes ,

[@preeti2525]

Noo q1 and q7 will be separated

[@hsg15]

no.. never because for 0 as well as for 1 input they are going to the same state . so they are totally equivallnce

[@iimoon777]

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}

[@yashparmar5722]

Thanks man love from india

[@TheMitsosS]

Amazing video!! You explain it really good!!

[@kaifahsan8459]

Amazing content. Thanks a lot Neso.

[@saipriya4700]

Thank you so much for clearing the concept

[@RahulSahu-yc9fc]

in 1 equivalence, how q6 is equivalent to q0 or q4?

[@Asdfdyutgfd]

same doubt

[@nkosinathikhumalo3989]

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.

[@naydernn4725]

Listening to this guy makes me feel so safe... Everything is explainable, everything is gonna be okay, don't worry 🥲

[@JoseAlvarez-dl3hm]

Awesome exponation. At last it clicked to me, lol.

[@gedelasivakrishna]

Thankyou !!

[@nottherealender]

15minutes before exam just enough time to watch the video 🤣🤣

[@uditisinha357]

while making the final transition table for minimized DFA can we write like {q1, q2} instead of q1q2? doesnt that make it NFA?

[@kavyahegade6477]

1 equivalence is not correct. q0,q4 are one set, q1,q6,q7 are one set. from there the mistake started

[@ashishgrover4506]

Sir how q6 is equal to q0 q4

[@godfatherop7526]

Thats a mistake , also q0 q7 wont be equal to q3 q5 but only q5

[@manishpawar5918]

There is no mistake please watch video with focus

[@thedestroyer505]

Are you dumb 😅

[@xenon384]

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

[@shubhammondal6403]

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?

[@mikhailwebb8377]

I was just wondering the same thing

[@OfficialQuerppMusic]

great video

[@kasturimeh]

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

[@TomShelbyXD]

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

[@shubhampithadiya2839]

is equivalence-3 saturates Q3 and Q5,?

[@rishavshah5842]

NO

[@SurajSingh-tf7dp]

You probably forgot to combine the states in the transition table, this was DFA .. so it could not have multiple states ... see 10:50

[@pratikgohil7821]

it is not multiple state, state name is {q1, q7}

[@dineshyadav08]

Ur excellent bro ....

[@sankarayachitula4328]

Excellent sir.

[@adityadhal5027]

in the transition table at the end {q0, q4} -> for 1 should be {q5} only. correct me if I'm wrong.

[@tejaltatiwar4682]

same doubt

[@omop5922]

Hey guys don't we remove unreachable states first before making equivalences?

[@berkberkmeen4748]

Yolu save my life .respect from turkey Comp.engineering department

[@namanpadiyar09]

Answer should be {q0, q4} {q6} {q1, q7} {q3,q5} {q2}.

[@vanshika5721]

q3 and q5 should be separate in equivalence of 3

[@syedzuhair2593]

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

[@muhammadashfaq8032]

You are right

[@subudhiroshni528]

For minimization of dfa first we have to remove unreachable state right?

[@srihari2541]

i didnt get it in the second equivalence

[@Lionelmessi-zp9vt]

yeah i too think its wrong in q2

[@macmascarenhas307]

Thank u. Good explanation

[@satyampenugurthi4365]

Sir you did a mistake at one equivalence as {q3,q5} should not fall in same set ,since they are going to final state

[@JESoutrik]

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 ?

[@uttkarshchavan9058]

Bot q2 is final state it can't be equivalent

[@pingalisaidireddy4138]

Tq sir now I'm getting clear about this topic

[@wellwisher2704]

Sir, does we need to construct a DFA state diagram at the end?

[@LordSarcasticVlogger]

I have some doubt…in what order we have to pick elements from Non-Final states list?

[@ayushmalhotra308]

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

[@ruchirai4406]

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...

[@uttkarshchavan9058]

Sir how q6 will group with q0 It will group with q1 4:45

[@anuradhasai7233]

very clear explanation....thank godd..!! and you sir!!

[@Zkanovic]

what if there is more than 1 final state? do I have to check if it is equivalance or not?

[@aishwarysharma3022]

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

[@rabbiipictures7505]

same problem I have, please if you know the solution, please tell me

[@soumilyade1057]

q3 is unreachable so it should be eliminated first.

[@soumilyade1057]

@@anitha9080 taking none of the input symbols, q3 can be reached from any of the other states. Hence, the string accepted never passes through the state q3.

[@swaraj6053]

@@soumilyade1057 I dont understand. What is wrong?

[@shakuntalakamade]

how does the q6 is 1 equivalent to q0 and q4?

[@gayathrinallam4487]

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?

[@yummycandy1703]

friend for 1 is q2 itself and for 0 the two equivalent states q0q4

[@manisharathour]

@@yummycandy1703 How it can be q0q4 for q2 ?

[@TANKALAHARSHAVARDHANBCT]

for doing q0 and q4 the q5 lies in different set right?

[@naitikbhavsar4195]

Yes that's what I'm confused abt

[@saeid4349]

How do you know that q2 is an exit state? How did you figure it out?

[@sasidharangs8125]

q3 is an unreachable state and must have been removed from the table even before we check equivalence right?

[@devanshsingh2]

Yeah i was thinking the same

[@username_0_0]

why q2X0={q0,q4 }? at 10:31

[@RohitKumar-zp6ci]

{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

[@adityaA627]

Q3 is a dead state as it is not reachable via any states so shouldn't it be a dead state and removed?

[@jokerharley2174]

In 2 equivalent (Q3,q5) are not 2 equivalent.

[@dattaramnavle6811]

similar output for same input

[@tinagourkar8766]

q3 is unreachable state so it should be eliminated right?

[@Serkanjim]

Great explanation! At first I thought you were doing it wrong, my bad :(

[@dilipjaiswal1201]

Sir minor mistake in solution Comparision of q0 and q4

[@i__sandesh]

Why didn't you remove the unreachable state first, i.e, q3 ???

[@avikbhanja]

Why is that unreachable?

[@dxlh8u574]

I still don't get it. In 1 equivalent how q0,q4, but how q6 is in the same state?

[@utpatang3596]

q3 should be omitted and there will be 6 states left

[@sukhchainloui2092]

This come in my final exam

[@shubhammandal4307]

Thanks

[@veeru-2023]

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. ❤

[@saurabhjindalvlogs874]

you did not remove unreachable state q3

[@parrotlover8302]

In Equivalence 1st not come q6 in q0 and q4

[@skumarn6435]

q3 is unreachable so can we remove it in initial stage only?

[@rishavshah5842]

YES THIS ONE..

[@lawkeeperray8832]

I'm curious, what is the Lm of this DFA?