Conversion of NFA to DFA
Вставка
- Опубліковано 15 вер 2024
- TOC: Conversion of Non-deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA).
Topics discussed:
1. This lecture shows how NFA and DFA are equivalent and how to convert an NFA to its equivalent DFA.
2. Equivalence of NFA and DFA.
3. Example of converting the NFA for a language that accepts all strings that starts with '0' to its equivalent DFA.
Full Course on TOC: goo.gl/f4CmJw
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Follow me on Instagram: @jaiz_itech (bit.ly/2M3xyOa)
Contribute: www.nesoacademy...
Memberships: bit.ly/2U7YSPI
Books: www.nesoacademy...
Website ► www.nesoacademy...
Forum ► forum.nesoacad...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#TheoryOfComputation #TOCByNeso #NFAtoDFA #NFA #DFA #AutomataTheory
You deserve an award. You've probably saved more lives than Superman.
Yes you are more than correct. After 3 weeks of classes in confusion, my questions were answered in 9 minutes
Please
Construct an optimized DFA :
0*1*(0/1)#
Exactly
are you an idiot??
@@sohammaity7389 I think you're the one
A day before the exam at 2x speed.
Technically day of for me (:
3 hours before the exam
more like 7 hours from exam.
Doing the same
During Online Exams from home :P...
I put aside my university study materials because they are useless (lack of explanation) for the sake of this course and instead of stomping around in one topic/exersize for a week, I have already gone through half the material in 3 days with examples. Thank you very much!
From having no knowledge about my compiler engineering subject to kickoff the subject like a master , I've come a long way with your teaching sir .... THANK YOU SO MUCH !!!
u have made the subject which i feared look damn easy, thanks a lot for your teaching, stay blessed sir
+1
I learned more in 10 minutes than I have in 8 weeks paying $1K in class. GPA savior.
then your class is shit.
You need to change ur classes bro
Waste of money. Universities should not be paid by students.
Especially useless subjects
I've been reading comments under algorithm tutorial videos and I learned more ways to flatter than to program
Appreciate your work, helping me a lot with automata theory. Very simple and detailed work, keep continuing it.
Thanks a lot, man! got a headache reading my lecture notes to figure it out but you put it pretty nicely!
Today I also converted to a DFA:
Definitely
Fixing-for
Academic Probation
Great videos! A correction maybe: In NFA the delta function goes from Q times sigma to P(Q). The power set. 2^|Q| is the cardinality of that set.
Yeah, though a lot of textbooks and resources use 2^Q as the notation for the Power Set, so that's probably just what he was used to
You’re the one that’s wrong. That notation is also used for the power set dumbass
This is the best example ever. Thanks a lot sir...... Tomorrow is my test and your explaination help me a lot
all your videos are good, easy to understand, well edited/produced. thank you. you are a good man!
Really helpful! Thanks a bunch. You make it practically trivial to understand
This example is too simple as the NFA & DFA are nearly identical
yeah, the main problem is when an NFA state has multiple transitions for the same symbol/
thanks for saving my cs career
Wow, your teaching style is a piece of cake.
Thanks a bunch.
OMG.....BEST EXPLANATION EVER.........!!!!!! Sir i dont know how shoud i thank you....
Contribute: www.nesoacademy.org/donate
This channel is a gem for engineering students.
Today I wrote my exam and I'm going to pass just because of you...🧡
sirf pass , atleast 2nd toh aa jate.
U Correct the paper then he will get 😂
very clear-cut explanation
good explanation sir
Why are there so many dislikes? I think this is an accurate video of NFA to DFA conversion.
Because some people always dislikes no matter how good the video is....
Because you cannot be successful if you don't have haters.
Because it is simply wrong. The example shows how to convert an incomplete DFA to a complete DFA. There is no nondeterminism in his automaton.
@@mouradqqch1767 Yes. Exactly the point.
👌👌👌🙏
This is not the technique of how to convert a NFA to DFA, which is more complicated than this. This video shows the technique of converting a non-complete DFA to a complete DFA. I think the technique is explained well but it is misleading.
He basicaly did convert non complete NFA to complete NFA. Lol dislike
@@lowzyyy The "NFA" in the example has no non-determinism, which means it is basically a DFA. Since the transition function is not fully defined, it is a non-complete DFA. The generic technique of converting an actual NFA to a DFA involves simulating the many possibilities of states the automata can be in at any moment in the computation by using 2^|Q| states, each representing a set of states of the NFA.
I am sure the intentions of the uploader were good, but the content does not actually teach the technique students are usually expected to understand when learning of NFA to DFA conversion.
Hate to break it to you.
YES, its annoying that he didnt correct the video.
@@Golha2505 @urizoran he has actually has more example videos you can check that out
its NFA, you're misleading
literally reading this 3 hours before my end sem exam.
Assignment ans: L2 -2 , L3 - 5 , L4 - 3 ,L5 - 5
i just wanted to remember this from my previous sem toc subject cause this is asked in my compiler design subject and this video is real bomb.....
This was incredibly easy to understand.
Wonderful explanation
Nesco is the best Tutorial Online Education (Thanks for being free I really cant afford even for Univercity easily)
Thankyou very much. It is very useful.
Very Very Amazing Class For Me.... Thanks Alots Sir🙏❤️
Best explanation. Go ahead!😍🥰
my teacher is big fan of you!!!!
Wooow glory to the Lord Neso academy admin you save my money for awhole semster😅😅😅
Wow. Brilliant 👏
Very Good tutorial in few minutes. Thanks. Cheers
Sir, the example you have taken is not a NFA, but that is DFA itself.
Why would I wanna convert? Is it because an NFA is easier to design but only a DFA can be implemented?
thank you so much!
Thanks for helping me before exams
Thank you neso academy
Please make tutorials on compiler design.
Sir plz tell me what is the correct answer for this question- Maximum number of states of a DFA converted from a NFA with n states is?
2^n
so basically, when it comes to NFAs that have only one next state for each symbol like the one in the video, it's equivalent DFA needs a specified transition for every alphabet symbol, can't just make it go nowhere (empty set)?
Your explanation is very nice
every DFA is an NFA , then if we are asked to design both DFA and NFA for some language , isn't it enough to just only design the
DFA ?
So what to do if the NFA has an empty string or lambda? For Example, a NFA is; S state goes to 1 when it gets a, then state 1 goes to state 2 when it gets b, and state 2 goes to S state when it gets a lambda/ empty string.
You're able to make everything look simple
thankyou so so much sir...God Bless You
Nice explanation of concept
love the intro.
this subject is hell it is so tough to learn uff
So converting using this state transition table.
sir the first example you showed for set of all strings that start with 0,why it needs a dead state?
If 1 comes to A ,can we show that it stays on A itself.
If you use your suggestion the automaton will accept any string that has at least a zero. The string 10 would be accepted. Which is not part of L
Thank you very much. Great video.
Thank you sir❤️
good lecture
In this video, you considered Phi as a new dead state in the NFA transition table, while in the coming videos you didn't create a dead state in the transition table of DFA! Could you please explain why?
phi in NFA means dead configuration (basically when a state does'nt goes anywhere after input ) in DFA it is then converted to dead state to make the DFA complete.
Thanks
Thank you so much Sir!
tjanks bro this so helpfull
The first explanation is not needed, it makes things sound very complicated. If shown first then explained theory it would make it much more easy to take it. Thank you.
thank you do much neso acadmy
@Final state, in the bases of what did you decide that AB is the final state!?
5*3 done
this is great, thanks bro
Boa sorte para TCOM pessoal!
assignment L1=4;L2=2;L3=5;L4=4;L5=5
Thankyou sir
How can I replace my incompetent professors with you? Thank you so much
Really helpful! Thanks a bunch :)
Awesome!
2 hours before exam up 24 hours and with 5 cups of coffee taken
What do you do if the same input is going to 2 different places. In one of my examples the 1 is going to A and B.
Bahut badiya
Tq very much
Kya chummeswari padha te hai sir 👌🏼
Thanks alot sir
Thank you!
First automaton is deterministic too!
can we take both 0 and 1 and go to the same state in case of DFA??
thanks sir!
Sir.... In NFA any state have multiple transition for any input... But in ur Example where it is... State A has only 1 transition for ip 0 and B also.
Is is NFA??
you are great sir
well explained
thank you sir
WARNING!!!!
I barley comment on UA-cam but I would like to warn ALL of you that although these videos are great for what they are, they MAY OR MAY NOT be accepted by your Professor. Neso's pumping lemma and NFA to DFA tutorials were marked completely wrong by my professor. I'm currently struggling to learn my professors specific way of how he would like the answers/ solutions and I highly advise everyone should pull up an example problem from neso and see if your professor gives you a thumbs up. Mines didn't!
What did your prof reject in-particular? The methods? The Answers were wrong? Are you justified with his specifics?
Your NFA is already a DFA!
mathematically every dfa is not an nfa. i do not know how to explain this because i cannot write mathemtical symbols here. But just go by the definition, and they are different. However NFA can be modified into a DFA
it was just wow!😱😱😱😱😱😱😱😱
The day before exam and watching 1.75x . thanks man
I love❤😘 this channel
thank you soo much dear .....respect and love for you
sir , but u said that DFA should be linear and every state should have 1 next state then why do we have 2 states in A when we convert NFA to DFA sir ?
You mixed the concepts of NFA and DFA
You are better than khan academy
I don't understand... at 04:15 you say "it is NFA" because input 1 from A goes nowhere (so basically phi). But why is that any of our concern? Shouldn't we only handle THE INPUTS THAT WE SEE (sry for caps, no anger intended; just for highlighting). I mean we can say it is NFA only if we apply the function for (same state, same input) and get two differente results... right? I do not understand your justification of why that is NFA.
Can you please specify a method to convert Dfa to anequivalent Nfa ?
Every DFA is a NFA
Wt about dfa to nfa sir??is this same for that
From where i can study computer organization and architecture??