exactly i don't know how that poor professors become permanent faculties of government institutes. My TOC teacher doesn't know how to use zoom for online classes. see wtf
dude same here bro. me also from govt institute. The institute hire professors by checking only their qualification like if they have phd from IIT then they are in .but they are not checking weather they have a skill to teach students.may be they are very rich in knowledge.
This may help : q1: Why C gets a self loop ? A1: Before C we have got our "aa" as required in "aabb", so any further a's do not disrupt our required sequence of "aabb" that is we cud still have "aaaa..ab" and still it will be valid since we got 2 a's in conjunction preceeding our b. q2: If C got a self loop, Why did we loop D to B and not create a self loop for it as well? A2: Before D we have got our "aab" as required in "aabb". If we create a self loop for D , we have end up with "aaba" which does not match our required string. In order to only get a "b" after "aab" we must go to the start (that is where our sequence started to form) since it will make our string "aaab" which is still valid and hope that when it reaches again to D we are getting input as "b".
Understood but why can't we send the input "a" from D to C instead of B, C has a self-loop of "a" so can we not still obtain "aab" if we send it to state C?
@@samalexander3295 That is because we can't predict what input will be ! So to make sure that we don't depend on ""Assumption"" and get the correct output. Explanation: You are correct about the the self loop of C that will give the desired output, but the problem will arise when we get b as input at C and the output will be """aabab""" which is wrong. Moral: So we have to check all the cases while solving DFA problems , else it will be incorrect.
A lot of confusion is going on here but i think this will help: "it's not the string 'aabb' that u have to achieve. It can be 'aaabbaa' or 'aabbaba' or any other string as long as it contains 'aabb' in it and the rest of the string can consist of any pattern.
@@shaifaliverma153 only aabb is also a solution.'our main idea is to make aabb as a substring for all the strings'. aabb is a substring of aabb as well.
@@rkogaming844 yaa i agree.....but what im saying is just.....that there's a big difference b/w a machine accepting only "aabb" and accepting "aabb" as a substring, because machine accepting only "aabb" is not gonna accept a string like "babbaabbab" which contains "aabb" as a substring.
It got from D to B for in put 'a' because after getting to B if we have another 'a' then our required string becomes "aa" when it reaches C and then the same process can continue again.If there had been a 'b' after jumping from D to B then it would go to A to start the whole process again as out string then would be "ab" and not "aa".
I have a question: From final state E, if we get another 'a', it's possible that we might get the sequence again so can't we move from state E to State B on receiving 'a' as input?
10:38 Why we need we sent back to state 'B' , as we have already achieved half of our string (i,e. aab). So now we need one more 'b', can we sent back from State 'D' to 'C' in order to get 'b'. I am confused here, help please🙌🙌
00:06 Constructing a DFA to accept strings over 'a' and 'b' without the sequence 'abb' 02:17 Construct a DFA over B that accepts 'aaBB'. 04:21 Deterministic Finite Automata in state transitions. 06:32 Deciding where to send inputs in a Finite Automata 08:41 State D transitions based on input B and a 10:44 Constructing a DFA that accepts all strings over a B that does not contain the string a a BB 12:50 Flipping the states to change the behavior of a DFA. 15:22 Designing a Deterministic Finite Automata for specific string patterns
I am starting a similar course in Uni. My lecture said solution might easy to understand but hard to figure it out. I guess now I knew what does that mean.
what can i say! hallelujah you saved my life the night before my exam , i was really lost in this topic but i don't even know how i got here , God really loves me . my God bless you abundantly your videos are just amazing . thanks so much
Thank you for providing such great content to help us learn properly. The example is pretty good and pretty perfect to use the flip technique to solve the problem. The explanation is pretty clear as well. Great job! And Thank you again!
These lectures have been really helpful! Thanks! One point about this one is that you could've written B the same way u did C and not had the C state at all
because after providing 'a' at state D, if you provide 'b' it reaches state E which is the final state, but the string would not contain aabb then.... so that makes the DFA wrong.
Please guys do watch from 16.40 bcoz its game changing point and its explained that why we interchange the states thanks alot! Helped alot still gng through vids
I guess we should to add a self loop (input b) for the final state D , cuz if we do not , the automata will reject for example all the strings "aabb*" or "abbaabb*" not just aabb . THANKS A LOT Neso Academy !
As it should. The question says to accept strings that does not "CONTAIN" aabb in it. As you can see "aabb*" or "abbaabb*" do "CONTAIN" aabb in them hence does need to be rejected.
No, if you send it to C state,(remember, before getting to D state we got b) then if the next state is bb and you send transition a to C then, its finish without having aabb with no way to go back. Look carefully, then you will notice.
sir plz upload a video for this video (DFA example-3) in any other way for the same example.... by solving by "Presence of aabb in the string"...creates some confusion..
I would like to make a comment on the step from D to B when a is the input (while doing the question when accepting any string containing aabb) We could have gone from D to C when input a is encountered.
It's confusing, but bare with me. Don't just read, try it on a piece of paper. Because, when we get to state D we have "aab". Now if we input "a" and go back to C, and in C we input "b", we will get "aabab" and advance back to D. So we will have "aabab" in D. So now if we add "b", it will go the final state as "aababb", but that's not what we want. So we would end up with an invalid string at the final state. We would end up with "aababb", which doesn't contain "aabb" as the problem requires.
@@gabrielsales7402 At D if we input 'a' and go back to A? Will that be wrong? Please do reply...I am really confused. I need to give my university exam.
@@indu5996 When you are at D, if you get an 'a' instead of a 'b' , it means that now you just have the first 'a' of the string that we want. So, instead of starting all over again from A, go to B because we just need 1 more 'a' in the string (the first one we got from D) before getting 'b'. If you go to A, you're not making use of the 'a' that you already have. Hope this helps..
Comparing both the example 2 (in the previous video) and this example 3, how am I supposed to know, whether the terminating state will go further or get self looped?
does the flipping of states work every time? like if you get any other problem, and then you first do the opposite of what is asked, then we flip the initial and final states? will it work?
No, if you send it to C state,(remember, before getting to D state we got b) then if the next state is bb and you send transition a to C then, its finish without having aabb with no way to go back. Look carefully, then you will notice.
@@bitethebyte bhai state D me agar a input aati hai toh aur hum state C me jaate hai agar toh hmaare pass C me pohanchne se pehle sequence hoga aab and pohanchne ke baad aaba then agar state C me input b aati hai toh sequence hoga aababb i.e, abb aur final state me pohanch jayenge jo ki galt hai and agar state B me jaate hai seedha D se then we got aabb and agar D se A me jaaate hai toh aaabb i.e, aabb so hum D se A and B me jaa sakte but C me nahi
Hey are you here? I have replied to yku one of your you tube comments about your DP contain housefly .it seems like a original flies is stick in my mobile 😁😁🤣
At first, I tried to find solution my own, when I do that I didn't consider simplification of problem. So I found 6 states and 1 state for exit. How can we decide which is lesser costly? extra 1 state or extra 3 final states for DFA?
quick question in state D in case we get an a cant we return it to state C instead of B, since it doesn't matter if it's an (a)aabb or aa(a)bb. note: the parenthesis to point out the a that came from state D
hey i want to mention that on getting input 'a' in state D you should transition back to state A because the string is disturbed if you get a combination 'aaba' , i think you might have missed that....
sir in transition at State D if we get to C for 'a' it should still work .... cuz even if we get 'a' it can loop in it self that is in C and then continue for b and so on plz correct me if I'm wrong🥲 I got rest of the things but I'm confuse at that part 🙂
You can still get 'b' in that state so it could form the string 'abb' instead of 'aabb' and reach the final state and that is incorrect Sorry for my broken English
No, if you send it to C state,(remember, before getting to D state we got b) then if the next state is bb and you send transition a to C then, its finish without having aabb with no way to go back. Look carefully, then you will notice.
hmmm, well if my initial state is also a finite state wouldn't this allow the machine to accept a false string? i mean, it will start with no input and it will be accepted..is a string of length 0 considered as a string?
as per me, you are correct. again, i have one more alternative i.e. from state D, if we perform self looping for input 'a', there too it satisfies the condition. Please respond if found true.
If you do State D to State C with input a, you can easily reached State E by doing abb, that why (e.g try aababb) You should have State D to State B so that to get to State E, you will need to do aabb again.
In the last example should there be another state off State A to make sure the length is 2 if you start with A, if I understand, if you start with b it will just return b with a length of b
I'm proud of you. Single handedly saving students that have poor professors.
Truee
exactly i don't know how that poor professors become permanent faculties of government institutes. My TOC teacher doesn't know how to use zoom for online classes. see wtf
dude same here bro. me also from govt institute. The institute hire professors by checking only their qualification like if they have phd from IIT then they are in .but they are not checking weather they have a skill to teach students.may be they are very rich in knowledge.
@@yashnarang637 Lol you answered your own question when you said "government".
The government can't run anything efficiently
Exactly.. 💕💕
This may help :
q1: Why C gets a self loop ?
A1: Before C we have got our "aa" as required in "aabb", so any further a's do not disrupt our required sequence of "aabb" that is we cud still have "aaaa..ab" and still it will be valid since we got 2 a's in conjunction preceeding our b.
q2: If C got a self loop, Why did we loop D to B and not create a self loop for it as well?
A2: Before D we have got our "aab" as required in "aabb". If we create a self loop for D , we have end up with "aaba" which does not match our required string. In order to only get a "b" after "aab" we must go to the start (that is where our sequence started to form) since it will make our string "aaab" which is still valid and hope that when it reaches again to D we are getting input as "b".
Understood but why can't we send the input "a" from D to C instead of B, C has a self-loop of "a" so can we not still obtain "aab" if we send it to state C?
@@samalexander3295 That is because we can't predict what input will be ! So to make sure that we don't depend on ""Assumption"" and get the correct output.
Explanation:
You are correct about the the self loop of C that will give the desired output, but the problem will arise when we get b as input at C and the output will be """aabab""" which is wrong.
Moral: So we have to check all the cases while solving DFA problems , else it will be incorrect.
@@revenant8061 Understood. Thank you for explaining.
@@revenant8061 thanks bro... i had same question
Thanks bro had the same doubt@@revenant8061
You're doing exceptional work. You're helping massive number of students pass their studies. Keep up the good work 🏆
A lot of confusion is going on here but i think this will help: "it's not the string 'aabb' that u have to achieve. It can be 'aaabbaa' or 'aabbaba' or any other string as long as it contains 'aabb' in it and the rest of the string can consist of any pattern.
It seems to me that it works fine.
......what we want is that "aabb" should be there as a substring in those strings....we don't want only aabb
we want the string,which "contains"(please note this word) aabb . Ok? ... "Not aabb alone"
@@shaifaliverma153 only aabb is also a solution.'our main idea is to make aabb as a substring for all the strings'. aabb is a substring of aabb as well.
@@rkogaming844 yaa i agree.....but what im saying is just.....that there's a big difference b/w a machine accepting only "aabb" and accepting "aabb" as a substring, because machine accepting only "aabb" is not gonna accept a string like "babbaabbab" which contains "aabb" as a substring.
I like how you give us multiple examples to work with, makes learning so easier!
It got from D to B for in put 'a' because after getting to B if we have another 'a' then our required string becomes "aa" when it reaches C and then the same process can continue again.If there had been a 'b' after jumping from D to B then it would go to A to start the whole process again as out string then would be "ab" and not "aa".
Thankyou
Sir but 11:06, D state can return to C state, it is not necessary to retun to B, because in C state there are two "a" transition already
nhi bhai we only consider the "a" we have in hand so we start building the "aabb" pattern again.
I have a question: From final state E, if we get another 'a', it's possible that we might get the sequence again so can't we move from state E to State B on receiving 'a' as input?
i dont think there will be better explanations than this .. thanks a lot for such amazing content !
You're an absolute genius sir, you saved my dreadful exams with the help of your absolutely amazing teaching! Thank you so much!
You did very well sir, the explanation was very clear. I cannot thank you enough 🙏
that is brilliant
i missed my first three lectures and i was lost but thank god i found you you life save
got an exam tomorrow, thanks for the explanation really helpful!
If there is an award like oscar in studies this man truly deserves 🙏🙏
10:38 Why we need we sent back to state 'B' , as we have already achieved half of our string (i,e. aab). So now we need one more 'b', can we sent back from State 'D' to 'C' in order to get 'b'. I am confused here, help please🙌🙌
same doubt, I had also sent it back to c ,if you find any contradict case pls comment...
This is a powerful example. I like question like these. These make sure you understand the concept. Thank you
00:06 Constructing a DFA to accept strings over 'a' and 'b' without the sequence 'abb'
02:17 Construct a DFA over B that accepts 'aaBB'.
04:21 Deterministic Finite Automata in state transitions.
06:32 Deciding where to send inputs in a Finite Automata
08:41 State D transitions based on input B and a
10:44 Constructing a DFA that accepts all strings over a B that does not contain the string a a BB
12:50 Flipping the states to change the behavior of a DFA.
15:22 Designing a Deterministic Finite Automata for specific string patterns
I am starting a similar course in Uni. My lecture said solution might easy to understand but hard to figure it out. I guess now I knew what does that mean.
what can i say! hallelujah you saved my life the night before my exam , i was really lost in this topic but i don't even know how i got here , God really loves me . my God bless you abundantly your videos are just amazing . thanks so much
at 10:15 we can also send it to state c right???
Awesome explanation sir! I recommend all my friends to watch your tutorials
Thank you for providing such great content to help us learn properly. The example is pretty good and pretty perfect to use the flip technique to solve the problem. The explanation is pretty clear as well. Great job! And Thank you again!
Where are you from?
Asking just out of curiosity 🤠
You are the G.O.A.T.
I should be paying you instead of my university lmao
goat???
@@vasutiwari4187 Greatest Of All Time
exceptionally good teaching , I am a final year student at University of Kwa Zulu Natal in South Africa and your videos help me a lot, thanks
These lectures have been really helpful! Thanks! One point about this one is that you could've written B the same way u did C and not had the C state at all
such a nice example, it helps us to understand the concept better!
Totally did not know we could flip a DFA. Awesome video :)
U were really awesome..keep rocking in many more students career 💯💯✨
thank you very much, the things i haven't learned from the past 6 months, you taught me in minutes.
neso is revolutionising the education. Thankyou very much for helping the students worldwide. you are doung great job.
at 11:12 minutes, why we have to send 'a' back to state B and why not we define self loop for 'a' to state D as state C ?
because after providing 'a' at state D, if you provide 'b' it reaches state E which is the final state, but the string would not contain aabb then.... so that makes the DFA wrong.
❤❤❤maja aagya is video mein to...thnx
Can we go to C also,after getting a on D?It also satisfies the sequence aabb.
maybe because if you get b in state C then it starts again so better be safe going to B
Why didn't we leave input b in B,why go back to A?
@@stephenodogwu7359 cz suppose after A→a→B→b→B we get an "a" then it'll proceed to C, that'll be an error. So it goes back to A.
@@manoranjanpanigrahi3677 aha thanks. It was easy!
THIS IS AMAZING!!!!! THANKS FOR THIS GREAT TUTORIAL!
Can I get your number for help
@@indronilbose haha bob n vagene pls
Sir ,did anyone forced the faculty to design these kind of subjects?
7 years later still better than proffessors rn
Thanks a lot with this course i got good amount of knowledge and able to do well in my vtu exams
12:07 couldn't we have state D as the final state with a self loop of 0,1?
Mine doubt is also the same.
Please guys do watch from 16.40 bcoz its game changing point and its explained that why we interchange the states thanks alot! Helped alot still gng through vids
Your starting music is awsome. I love it😍😍
I hate that music :( please change and add some pleasant music over here
tidim tim tim...,tidim tim tidim tim tim.....
@@RTXzenith 🤣🤣🤣
@@deepudakshu why u hate? Its good music ok
I had to watch it twice to understand. It made sense the second time.
Thank you sir! Your step by step tutorial is so clear and understandable.
that was simply genius,thanks for these lectures NESO ACADEMY
Leluch vi britania
@@usamatahseenulhaque9125 Lmao, zero fan
I guess we should to add a self loop (input b) for the final state D , cuz if we do not , the automata will reject for example all the strings "aabb*" or "abbaabb*" not just aabb . THANKS A LOT Neso Academy !
As it should. The question says to accept strings that does not "CONTAIN" aabb in it. As you can see "aabb*" or "abbaabb*" do "CONTAIN" aabb in them hence does need to be rejected.
what is the problem when i make transition from d to c over a instead of d to b over a?
please give me the exact ans asa soon as possible
@@ARWORLD-xw8ph I did the same while solving. I think that works well..
No, if you send it to C state,(remember, before getting to D state we got b) then if the next state is bb and you send transition a to C then, its finish without having aabb with no way to go back. Look carefully, then you will notice.
Check what happens for the string aabaabb
At 12:00 it should go form D to C such that we already have aa
9:35 State D receiving an 'a' implies that to quickest reach the successful state would be for 'abb' to follow--that is the situation in state B.
D->C for a
11:56 If I make the state E as self-loop then it can accept aabb & whatever input is! is that possible?
I am thinking the same
@@usamatahseenulhaque9125 do you have any soluiton, because I am thinking the same
you are a life saver. thank you for explaining so clearly
Wonderful teacher, thank you for all your help.
Input 'a' on D will go to C instead of B as if it goes to C then it forms aabaaaabb
As there is a self loop on C is present
If we do that, and if we get an input lets say "aababb", it will get accepted even if it does not contain the string "aabb" in it.
@@anushasinha24 finally got it, thanks
why not aabaabb ??
sir plz upload a video for this video (DFA example-3) in any other way for the same example....
by solving by "Presence of aabb in the string"...creates some confusion..
I would like to make a comment on the step from D to B when a is the input (while doing the question when accepting any string containing aabb)
We could have gone from D to C when input a is encountered.
according to your suggestion, "aababa" will be accepted. look closely, you will reach the final state without having aabb in your string
@@samarth638 yes.
On giving aabababb, the input is accepted but it does not suffice our conditions.
Sir when the input is 'a' in stante D, then why not send in state C
Same doubt
It's confusing, but bare with me. Don't just read, try it on a piece of paper. Because, when we get to state D we have "aab". Now if we input "a" and go back to C, and in C we input "b", we will get "aabab" and advance back to D. So we will have "aabab" in D. So now if we add "b", it will go the final state as "aababb", but that's not what we want. So we would end up with an invalid string at the final state. We would end up with "aababb", which doesn't contain "aabb" as the problem requires.
@@gabrielsales7402 Nice explanation
I understood it
@@gabrielsales7402 At D if we input 'a' and go back to A? Will that be wrong? Please do reply...I am really confused. I need to give my university exam.
@@indu5996
When you are at D, if you get an 'a' instead of a 'b' , it means that now you just have the first 'a' of the string that we want. So, instead of starting all over again from A, go to B because we just need 1 more 'a' in the string (the first one we got from D) before getting 'b'. If you go to A, you're not making use of the 'a' that you already have.
Hope this helps..
U explain tough topics very easily.....thank u sr
BRO WTH IM LEARNING SO MUCH I HAVE MY EXAM ON FRIDAY AND THIS HELPS ME SO MUCHO, LOVE YOU. I'LL TELL YOU WHAT HAPPENED ON THAT DAY...
what happendd
@@chinmaygaming3827 Lol, I didn't remember this. I passed the exam with the minimum. It was a complete win for me.
finally I start to understand what is actually is DFA mean . Thank you very much
Thanks a lot, Neso Academy for saving us...
Please continue this good work you will get love from students
Comparing both the example 2 (in the previous video) and this example 3, how am I supposed to know, whether the terminating state will go further or get self looped?
I still confused
@dangeroux can please tell best online source to study theory of automata for college level since in neso video example are less
@dangeroux and from where you solve question which book Or source
Sir your explanation is very well.
Sir you make video only for gate
we can also Send state D to C with input a instead of D TO B both give the output right
Thank you fot teaching this trick... I socred higher in examl......
thanks a lot...
You are the real reason by which I got grades
At 11:00 from D to B is great but we could have also done D to A, right?
hai sir, doing great job. requesting to upload lectures on DIGITAL COMMUNICATION. we are in great need. thank u
does the flipping of states work every time?
like if you get any other problem, and then you first do the opposite of what is asked, then we flip the initial and final states? will it work?
Fully understable explanation
the string should accept over {a,b} right, in the final answer the initial state only is been the final state also then that could make {a or b} ??
Very good job sir... I am actually helped a lot in understanding the concept with examples!
Getting input "a" in state D cant we send it to A,B and C ? the sequence is alright.
No, if you send it to C state,(remember, before getting to D state we got b) then if the next state is bb and you send transition a to C then, its finish without having aabb with no way to go back. Look carefully, then you will notice.
@@michaelfanai4579 can you please explain it in other words
@@bitethebyte bhai state D me agar a input aati hai toh aur hum state C me jaate hai agar toh hmaare pass C me pohanchne se pehle sequence hoga aab and pohanchne ke baad aaba then agar state C me input b aati hai toh sequence hoga aababb i.e, abb aur final state me pohanch jayenge jo ki galt hai and agar state B me jaate hai seedha D se then we got aabb and agar D se A me jaaate hai toh aaabb i.e, aabb so hum D se A and B me jaa sakte but C me nahi
@@vishalrikhi4297 thanks bro
pleasant explanation with perfect examples....thank you very much sir.
you are better than %99 of the professors
@ 5:09, why does the state goes from B to A after getting an input b, rather than looping to itself?
Going back to A means we need to start again. Self loop will mean we can have abbbbbbbb*{a,b}*
Brilliant explanation!
The best class!
I think from state D if we get input a we should go to state C.But you made it to go to state B.please clarify.
Bro i was so confused when ma'am was teaching 😥...but now all my doubts are clear some how😅
In two days, I am having my TOC exams and I'm starting the syllabus now :)
You Sir, are a great man! Thank you.
Hey are you here? I have replied to yku one of your you tube comments about your DP contain housefly .it seems like a original flies is stick in my mobile 😁😁🤣
@@shyamprakashm6325 Ha Ha, Great to see you again 🤣
At first, I tried to find solution my own, when I do that I didn't consider simplification of problem. So I found 6 states and 1 state for exit. How can we decide which is lesser costly? extra 1 state or extra 3 final states for DFA?
quick question in state D in case we get an a cant we return it to state C instead of B, since it doesn't matter if it's an (a)aabb or aa(a)bb. note: the parenthesis to point out the a that came from state D
Thank you for these lectures. May the Creator bless you.
Thank you sir! Good example and even better explanation!
hey i want to mention that on getting input 'a' in state D you should transition back to state A because the string is disturbed if you get a combination 'aaba' , i think you might have missed that....
In the string 'aaba,' there is already an 'a' at the end. If you go back to state A, then there will be 'aaa' in the string.
sir in transition at State D if we get to C for 'a' it should still work .... cuz even if we get 'a' it can loop in it self that is in C and then continue for b and so on
plz correct me if I'm wrong🥲
I got rest of the things but I'm confuse at that part 🙂
You can still get 'b' in that state so it could form the string 'abb' instead of 'aabb' and reach the final state and that is incorrect
Sorry for my broken English
This is great. I didn’t see that trick in Sipser.
10:58
Didn't get that.
if we get aab'aabb'..
C will loop double a and move further to D and then E
Is it the only solution or we can have any other solution for the problem ?
The input 'a' from state D can be sent to state C also?
No, if you send it to C state,(remember, before getting to D state we got b) then if the next state is bb and you send transition a to C then, its finish without having aabb with no way to go back. Look carefully, then you will notice.
if the set includes all strings except aabb then the self recursive loops of E should go back to some other states right?
WOW GREAT SIR YOU EXPLAINED VERY WELL :)
hmmm, well if my initial state is also a finite state wouldn't this allow the machine to accept a false string? i mean, it will start with no input and it will be accepted..is a string of length 0 considered as a string?
Apostolos Mavropoulos DFA does not accept epsilon, strings with length 0.it will not start.
Thanks so much. I will recomment my friends to come here.
At 11.12 second from state D to State C also can be done for input 'a' and that satisfies the condition. Can any one try and confirm?
as per me, you are correct. again, i have one more alternative i.e. from state D, if we perform self looping for input 'a', there too it satisfies the condition. Please respond if found true.
Exactly what I was wondering but there's no confirmation to it
If you do State D to State C with input a,
you can easily reached State E by doing abb, that why (e.g try aababb)
You should have State D to State B so that to get to State E, you will need to do aabb again.
Correct
In the last example should there be another state off State A to make sure the length is 2 if you start with A, if I understand, if you start with b it will just return b with a length of b
Nice approach. Thanks it helped me in solving another problem of my book
Great explanation. Can there be different answers that are correct?
Thank you so much sir
Love from muzaffer garh Pakistan
Best explanation ever