Machines | Convert NFA to DFA
videos | at work | information | view | construction
Learn to convert a nondeterministic finite state automaton (NFA) to a deterministic finite state automaton (DFA). This is part of a series of videos about regular expressions and finite state automata as part of a course in discrete structures.
Comments
-
what would you do in the scenario where you drawing the second chart, and your inititial state only has epsilon arcs going out?
-
Perfect
-
I've got the lambda notation, I presume it's a logical equivalent of epsilon star?
-
when you create the "aE*|bE*|cE*" table and you get to the row 2,1 what happens if 'a' took you to somwhere on both two and one which one would you choose. i.e 1a->2 and 2a->3?
-
Please, can you tell me what is the program that you use it to record this tutorial?
-
what would you do in the scenario where you drawing the second chart, and your inititial state only has epsilon arcs going out?
-
Thank you very much! I finally realised how to transform a NFA. Especially thank you for explaining how to expand epsilons, because that was the thing I had been doing wrong. Thank you!!!
-
This helped. Thanks
-
what is the name of this method? subset construction or thomson's construction?
-
is ths the subset construction method that is in the dragon book ?
-
omg thanks man, you're the best
-
Doesn't work if your startingpoint has only epsilon transitions going out and nothing coming in, (for instance if you want to OR/unite two NFAs via a new startingstate that has an epsilon transition to the startingstate of each of the original 2 machines) that way u would have a blank in the first grid at 1a 1b and 1c. Only 1epsilon* would lead to other states.
If you can't do a, then you can't do aepsilon* which means the second grid 1aepsilon* and 1bepsilon* would also have no states --> starting states has no connecion to any other state. :/ -
Very helpful if you have a smaller DFA but becomes really hard to manage as the NFA grows.
-
What if the start state has only epsilon transitions? How can we convert that into a DFA? Something similar to this : http://imgur.com/yr2mbBl
unable to create the second table as the start state gives blank for both columns 0E* and 1E* -
many many thanks for good jobs
-
thnks for this video you help me to my exam :)
-
Excellent!
-
something is not right here
-
As I learned it, this isn't a final DFA; you need to add a trap state for transitions not charted; eg, 1 c -> trap; 4,3 b -> trap; 3 c -> trap; 3 b -> trap.
-
excellent!