Computation 10 : NFA to DFA 1(powerset construction)

نظرية الحوسبه دكتور نذيرغرايبه 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