Conversion of NFA to DFA
HTML-код
- Опубликовано: 6 сен 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 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
u have made the subject which i feared look damn easy, thanks a lot for your teaching, stay blessed sir
+1
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 !!!
I've been reading comments under algorithm tutorial videos and I learned more ways to flatter than to program
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/
Today I also converted to a DFA:
Definitely
Fixing-for
Academic Probation
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!
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
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
thanks for saving my cs career
Really helpful! Thanks a bunch. You make it practically trivial to understand
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 😂
good explanation sir
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
Assignment ans: L2 -2 , L3 - 5 , L4 - 3 ,L5 - 5
all your videos are good, easy to understand, well edited/produced. thank you. you are a good man!
OMG.....BEST EXPLANATION EVER.........!!!!!! Sir i dont know how shoud i thank you....
Contribute: www.nesoacademy.org/donate
Why would I wanna convert? Is it because an NFA is easier to design but only a DFA can be implemented?
This channel is a gem for engineering students.
Wow, your teaching style is a piece of cake.
Thanks a bunch.
very clear-cut explanation
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)?
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.
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.
👌👌👌🙏
Nesco is the best Tutorial Online Education (Thanks for being free I really cant afford even for Univercity easily)
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
Wooow glory to the Lord Neso academy admin you save my money for awhole semster😅😅😅
literally reading this 3 hours before my end sem exam.
This was incredibly easy to understand.
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.....
Thankyou very much. It is very useful.
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 ?
my teacher is big fan of you!!!!
Wonderful explanation
Sir, the example you have taken is not a NFA, but that is DFA itself.
this subject is hell it is so tough to learn uff
So converting using this state transition table.
Very Very Amazing Class For Me.... Thanks Alots Sir🙏❤️
Best explanation. Go ahead!😍🥰
Thanks for helping me before exams
Wow. Brilliant 👏
Very Good tutorial in few minutes. Thanks. Cheers
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.
Please make tutorials on compiler design.
Thank you neso academy
Your explanation is very nice
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.
can we take both 0 and 1 and go to the same state in case of DFA??
thank you so much!
You're able to make everything look simple
How can I replace my incompetent professors with you? Thank you so much
love the intro.
@Final state, in the bases of what did you decide that AB is the final state!?
Nice explanation of concept
Why b is not a dead state please reply sir
thankyou so so much sir...God Bless You
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??
Wt about dfa to nfa sir??is this same for that
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 ?
Can you please specify a method to convert Dfa to anequivalent Nfa ?
Every DFA is a NFA
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.
Thank you very much. Great video.
From where i can study computer organization and architecture??
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
Thanks
thank you do much neso acadmy
Thank you sir❤️
assignment L1=4;L2=2;L3=5;L4=4;L5=5
I am not quite sure if this it correct when you say DFA has Q state and NFA has 2^Q. Because in the book intro to automata and computation page 61. It says the opposite.... can someone answer my question? Thanks!
Thank you so much Sir!
5*3 done
good lecture
how we get the final state with the help of transition diagram??
pls anyone reply
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.
First automaton is deterministic too!
Is this subset construction
Sir convert the below DFA diagram to its equivalent NFA diagram .give me this answer please .
Q0--------(-q1)0
( q2)0.1
what if the NFA contain lambda?
Kya chummeswari padha te hai sir 👌🏼
this is great, thanks bro
Really helpful! Thanks a bunch :)
You are better than khan academy
tjanks bro this so helpfull
WARNING!!!!
I barley comment on RUclips 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?
Boa sorte para TCOM pessoal!
Dunno if there is some comment censorship but content of video does not match the title. You claim to convert NFA to DFA but in the video you instead convert DFA without a complete transition function to DFA with complete transition function. If you were to begin with NFA you would have multiple options to move to different state with say character 0.
Dunno if people are just so stupid or comments are being deleted but this is misinforming video.
Thankyou sir
well explained
you are great sir
thanks sir!
2 hours before exam up 24 hours and with 5 cups of coffee taken
Tq very much
Thank you!
Sir The string Should start with 0 ,Will the automata accept it if it starts with 1???? If not Why should we have the State C in DFA ???? Pls do clear this Sir .Thanks you Sir in advance
NFA doesn't require a trap state, as every undefined state transition means that undefined transition won't produce language / language subset. I got this information here...
www.quora.com/Is-there-a-trap-state-in-a-non-deterministic-finite-state-automata
because DFA is a complete system we need to specify states for every input alphabets . even if we don't require it for the langauage acceptance so, we put them in dead/trap state
Bahut badiya
Awesome!