NFA to DFA Conversion Explained: Powerset Construction Method 🧮

نظرية الحوسبه
دكتور نذيرغرايبه

1:25 although NFA and DFA are different. they are equal
2:01 Animated NFA
Note the difference in Transition Function and Transition Table 4:05
5:30 Take care of Lambda Transitions, considered a special case 6:38
12:25 Q) What is the Language of this NFA?
15:30 NFAs accept the Regular Languages
Equivalence of Machines
Example of equivalent machines
18:06 NFAs and DFAs have the same computation power,
accept the same set of languages
19:17 more discussion about NFAs and DFAs
21:10 return to Homework 1

NFAs are interesting because we can express languages easier than DFAs

23:18 What do we know about this language’s automaton?
a*b*


30:00 Can you give a DFA that accepts the
complement of this language


32:00 An NDFA can be non-deterministic by:
three conditions


40:00 NFA to DFA 1(powerset construction)


Rabin–Scott powerset construction (or subset construction) to distinguish it from similar constructions for other types of automata, was first published by Michael O. Rabin and Dana Scott in 1959

Finite Automata and Their Decision Proble’ms, 1957 ,
https://pdfs.semanticscholar.org/5b5d/dfc2a0bfc5a048461eb11c191831cd226014.pdf?_ga=2.160337277.1908349912.1602263546-1369773474.1602263546

“The logic of automata,” 1957
https://deepblue.lib.umich.edu/bitstream/handle/2027.42/3967/bab6288.0001.001.pdf?sequence=5&isAllowed=y