Microsoft PowerPoint – CS332-Lec04-ann
BU CS 332 – Theory of Computation
Lecture 4:
• More on NFAs
• NFAs vs. DFAs
• Closure Properties
Reading:
Sipser Ch 1.1‐1.2
Mark Bun
February 3, 2021
Last Time
• Deterministic Finite Automata (DFAs)
• Informal description: State diagram
• Formal description: What are they?
• Formal description: How do they compute?
• A language is regular if it is recognized by a DFA
• Intro to Nondeterministic FAs
2/3/2021 CS332 ‐ Theory of Computation 2
Nondeterminism
2/3/2021 CS332 ‐ Theory of Computation 3
1 0
1
0 1
0,1
0
A Nondeterministic Finite Automaton (NFA) accepts if
there exists a way to make it reach an accept state.
Some special transitions
2/3/2021 CS332 ‐ Theory of Computation 4
0
0, 1
1
𝜀‐transitions
(don’t consume a symbol)
Multiple
transitions
No transition
Example
2/3/2021 CS332 ‐ Theory of Computation 5
0,1
0,10
a)
b)
c)
d)
Formal Definition of a NFA
2/3/2021 CS332 ‐ Theory of Computation 6
is the set of states
is the alphabet
is the transition function
0 is the start state
is the set of accept states
An NFA is a 5‐tuple 0
accepts a string if there exists a path from 0 to
an accept state that can be followed by reading .
Example
2/3/2021 CS332 ‐ Theory of Computation 7
0,1
0, 1
0,1
1
𝟏 𝟐 𝟑𝟎
𝟎
𝟎, 𝟏 𝟐 𝟑
𝟑
𝟎
𝟐
𝟎
𝟏
Nondeterminism
2/3/2021 CS332 ‐ Theory of Computation 8
Ways to think about
nondeterminism
• (restricted)
parallel
computation
• tree of possible
computations
• guessing and
verifying the
“right” choice
Deterministic
Computation
Nondeterministic
Computation
accept or reject accept
reject
Why study NFAs?
• Not really a realistic model of computation: Real
computing devices can’t really try many possibilities in
parallel
But:
• Useful tool for understanding power of DFAs/regular
languages
• NFAs can be simpler than DFAs
• Lets us study “nondeterminism” as a resource
(cf. P vs. NP)
2/3/2021 CS332 ‐ Theory of Computation 9
NFAs can be simpler than DFAs
2/3/2021 CS332 ‐ Theory of Computation 10
An NFA for this language:
1
0
0,10
A DFA that recognizes the language
:
1
0,1
1
0,1
0
0
Equivalence of NFAs and
DFAs
2/3/2021 CS332 ‐ Theory of Computation 11
Equivalence of NFAs and DFAs
Every DFA is an NFA, so NFAs are at least as powerful as
DFAs
Theorem: For every NFA , there is a DFA such that
Corollary: A language is regular if and only if it is
recognized by an NFA
2/3/2021 CS332 ‐ Theory of Computation 12
Equivalence of NFAs and DFAs (Proof)
2/3/2021 CS332 ‐ Theory of Computation 13
Let 0 be an NFA
Intuition: Run all threads of in
parallel, maintaining the set of
states where all threads are.
accept
reject
Goal: Construct DFA 0 recognizing
Formally:
“The Subset Construction”
NFA ‐> DFA Example
2/3/2021 CS332 ‐ Theory of Computation 14
1
a b
Subset Construction (Formally, first attempt)
2/3/2021 CS332 ‐ Theory of Computation 15
for all and .
0
Input: NFA 0
Output: DFA 0
Subset Construction (Formally, for real)
2/3/2021 CS332 ‐ Theory of Computation 16
∈ for all and .
0 0
contains some accept state of
Input: NFA 0
Output: DFA 0
NFA ‐> DFA Example
2/3/2021 CS332 ‐ Theory of Computation 17
0,1
ε 0
b ca
1
Proving the Construction Works
Claim: For every string , running on leads to state
There exists a computation path
of on input ending at
Proof idea: By induction on
2/3/2021 CS332 ‐ Theory of Computation 18
Historical Note
Subset Construction introduced in Rabin & Scott’s 1959
paper “Finite Automata and their Decision Problems”
2/3/2021 CS332 ‐ Theory of Computation 19
1976 ACM Turing Award citation
For their joint paper “Finite Automata and
Their Decision Problem,” which introduced
the idea of nondeterministic machines,
which has proved to be an enormously
valuable concept. Their (Scott & Rabin)
classic paper has been a continuous source
of inspiration for subsequent work in this
field.
NFA ‐> DFA: The Catch
If is an NFA with states, how many states does the
DFA obtained using the subset construction have?
a)
b)
c)
d) None of the above
2/3/2021 CS332 ‐ Theory of Computation 20
Is this construction the best we can do?
Subset construction converts an state NFA into a ‐state
DFA
Could there be a construction that always produces, say, an
‐state DFA?
Theorem: For every , there is a language such that
1. There is an ‐state NFA recognizing .
2. There is no DFA recognizing with fewer than
states.
Conclusion: For finite automata, nondeterminism provides an
exponential savings over determinism (in the worst case).
2/3/2021 CS332 ‐ Theory of Computation 21
Closure Properties
2/3/2021 CS332 ‐ Theory of Computation 22
An Analogy
In algebra, we try to identify operations which are
common to many different mathematical structures
2/3/2021 CS332 ‐ Theory of Computation 23
Example: The integers are
closed under
• Addition:
• Multiplication: ×
• Negation:
• …but NOT Division:
We’d like to investigate similar closure properties of the
class of regular languages
Regular operations on languages
Let ∗ be languages. Define
Union:
Concatenation:
Star: ∗
2/3/2021 CS332 ‐ Theory of Computation 24
Other operations
Let ∗ be languages. Define
Complement:
Intersection:
Reverse:
2/3/2021 CS332 ‐ Theory of Computation 25
Closure properties of the regular languages
Theorem: The class of regular languages is closed under
all three regular operations (union, concatenation, star),
as well as under complement, intersection, and reverse.
i.e., if and are regular, applying any of these
operations yields a regular language
2/3/2021 CS332 ‐ Theory of Computation 26