ECS 120 Lecture Notes - Lecture 3: Regular Expression, The Algorithm
31 May 2018
School
Department
Course
Professor
LECTURE 7
DFA VS NFA
1. For NFA can have multiple arrows for one state and one symbol
2. DFA’s can only have one arrow per state and symbol
3. Empty = epsilon this can be used in NFA,
a. The empty epsilon�is used to denote that no character is read.
What makes the above a NFA and not a DFA?
1. Notice at q1, there are two transitions possible
a. Q1, 1 → q1
b. Q1,1 → q2
2. So which of these paths are taken?
a. Both paths are taken, the NFA is powerful enough that it takes all possible paths
and explores all of the paths for the full string
b. If any path can lead to an accept, the machine will accept.
3. What language is accepted by the NFA give some strings?
a. 11, 0101, 0111, 000001101010101,
b. Is there any string that's not accepted?
Are NFA’s more powerful than DFA’s?
1. No
a. Any NFA can be made into a DFA.
2. So why have NFA’s
a. NFA’s are easier to build.
b. When building a machine for a language, most of the time people build the NFA
first and then reduce.
find more resources at oneclass.com
find more resources at oneclass.com
3.
4. Why is the above NFA so cool?
a. In DFA’s it would be very hard to express how to check if a 1 is 3rd from the end.
But this NFA can do such a thing with only 4 states.
Lecture 8 example of successive refinement algorithm
find more resources at oneclass.com
find more resources at oneclass.com
This is not tested
find more resources at oneclass.com
find more resources at oneclass.com
