BU CS 332 – Theory of Computation
Lecture 3:
• Nondeterminism
Reading:
Sipser Ch 1.1‐1.2
• Equivalence of NFAs and DFAs
• More on closure properties
Mark Bun January 29, 2020
Nondeterminism
1
0,1 01
0 1
A Nondeterministic Finite Automaton (NFA) accepts if there is a way to make it reach an accept state.
1/29/2020 CS332 ‐ Theory of Computation 2
0
Nondeterminism
1
0,1 01
0 1
Example: Does this NFA accept the string 1100?
1/29/2020 CS332 ‐ Theory of Computation
3
0
Some special transitions
1/29/2020
CS332 ‐ Theory of Computation 4
0
0, 1
1
Example
1/29/2020
CS332 ‐ Theory of Computation 5
0
1
0
Example
0,1
1 0, 1
0,1
1/29/2020 CS332 ‐ Theory of Computation
6
Formal Definition of a NFA
An NFA is a 5‐tuple is the set of states
0
is the alphabet
is the transition function
0 is the start state
is the set of accept states
accepts a string if there exists a path from an accept state that can be followed by reading
0 to .
1/29/2020 CS332 ‐ Theory of Computation
7
Example
1
1/29/2020
CS332 ‐ Theory of Computation
8
𝟐
𝟒
𝟏
0
𝟎, 𝟏 𝟐 𝟑 𝟒 𝟒
0
𝟎 𝟑
𝟎
𝟐 𝟑
Example
1/29/2020
CS332 ‐ Theory of Computation 9
0,1
1 0, 1
0,1
𝟎𝟏𝟐𝟑
𝟑
𝟏 𝟐
𝟎
𝟎 𝟎
𝟎, 𝟏 𝟐 𝟑
Nondeterminism
Deterministic Computation
Nondeterministic Computation
accept or reject
accept
• guessing and verifying the “right” choice
1/29/2020
CS332 ‐ Theory of Computation
10
reject
• tree of possible computations
Ways to think about nondeterminism
• (restricted) parallel computation
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)
1/29/2020 CS332 ‐ Theory of Computation 11
NFAs can be simpler than DFAs
A DFA that recognizes the language : 0
0,1
An NFA that recognizes the language
:
1/29/2020 CS332 ‐ Theory of Computation
12
1
0,1
1
Sometimes DFAs must be larger
Theorem. Every DFA for the language must have at
least 3 states.
Proof:
1/29/2020 CS332 ‐ Theory of Computation 13
Equivalence of NFAs and DFAs
1/29/2020 CS332 ‐ Theory of Computation 14
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
1/29/2020 CS332 ‐ Theory of Computation 15
Equivalence of NFAs and DFAs (Proof)
Let 0 Goal: Construct DFA
beanNFA
0 recognizing
1/29/2020
CS332 ‐ Theory of Computation 16
accept
reject
Intuition: Run all threads of in parallel, maintaining the set of states where all threads are.
Formally:
“The Subset Construction”
NFA ‐> DFA Example
1/29/2020
CS332 ‐ Theory of Computation
17
a
1
b
Subset Construction (Formally)
Input: NFA Output: DFA
0
0
forall and .
0
1/29/2020
CS332 ‐ Theory of Computation 18
NFA ‐> DFA Example
0,1
1ε203 1
1/29/2020 CS332 ‐ Theory of Computation 19
Subset Construction (Formally)
Input: NFA Output: DFA
0
0
∈
for all
and .
0 0
contains some accept state of
1/29/2020
CS332 ‐ Theory of Computation
20
Proving the Construction Works
Claim: For every string , running on There exists a computation
leads to state
of on input ending at Proof idea: By induction on
1/29/2020 CS332 ‐ Theory of Computation
21
Historical Note
Subset Construction introduced in Rabin & Scott’s 1959 paper “Finite Automata and their Decision Problems”
1/29/2020
CS332 ‐ Theory of Computation 22
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.
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).
1/29/2020 CS332 ‐ Theory of Computation 23