BU CS 332 – Theory of Computation
Lecture 3:
• Nondeterminism
• Equivalence of NFAs and DFAs
• More on closure properties
Mark Bun January 29, 2020
Reading:
Sipser Ch 1.1-1.2
Nondeterminism 1
0 1
0
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
Nondeterminism 1
0 1
0
01
0,1
Example: Does this NFA accept the string 1100?
1/29/2020 CS332 – Theory of Computation
3
Some special transitions
0𝜺𝜺 0, 1
1
1/29/2020
CS332 – Theory of Computation 4
Example
𝜺𝜺 𝜺𝜺
0
1
0
𝑳𝑳(𝑴𝑴) =
1/29/2020
CS332 – Theory of Computation
5
Example
0,1
1 0,𝜺𝜺 1
0,1
𝑳𝑳(𝑴𝑴) =
1/29/2020
CS332 – Theory of Computation
6
AnNFAisa5-tuple𝑀𝑀 = (𝑄𝑄,Σ,δ,𝑞𝑞 ,𝐹𝐹)
Formal Definition of a NFA
0
𝑄𝑄 is the set of states
Σ 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 𝑞𝑞 to 0
an accept state that can be followed by reading 𝑤𝑤. 1/29/2020 CS332 – Theory of Computation 7
Example 𝒒𝒒 𝒒𝒒𝜺𝜺𝟐𝟐1
𝒒𝒒𝟒𝟒
𝟎𝟎 𝒒𝒒 0
𝑴𝑴 = (𝑸𝑸,𝚺𝚺,δ,𝑸𝑸𝟎𝟎,𝑭𝑭) 𝑸𝑸 = {𝒒𝒒𝟎𝟎,𝒒𝒒𝟏𝟏,𝒒𝒒𝟐𝟐,𝒒𝒒𝟑𝟑,𝒒𝒒𝟒𝟒}
𝜺𝜺
𝟑𝟑
δ(𝒒𝒒𝟐𝟐,𝟏𝟏) =
𝒒𝒒𝟏𝟏
0
𝚺𝚺= {𝟎𝟎,𝟏𝟏} 𝑭𝑭 = {𝒒𝒒𝟒𝟒}
1/29/2020
δ(𝒒𝒒𝟑𝟑,𝟏𝟏) =
CS332 – Theory of Computation 8
Example
0,1
𝒒𝒒𝟎𝟎 1 𝒒𝒒𝟏𝟏 0,𝜺𝜺 𝒒𝒒𝟐𝟐 1 𝒒𝒒𝟑𝟑
0,1
𝑵𝑵 = (𝑸𝑸,𝚺𝚺,δ,𝒒𝒒𝟎𝟎,𝑭𝑭) 𝑸𝑸 = {𝒒𝒒𝟎𝟎, 𝒒𝒒𝟏𝟏, 𝒒𝒒𝟐𝟐, 𝒒𝒒𝟑𝟑}
δ(𝒒𝒒𝟎𝟎,𝟎𝟎) = δ(𝒒𝒒𝟎𝟎,𝟏𝟏) =
𝚺𝚺 = {𝟎𝟎,𝟏𝟏}
𝑭𝑭 = {𝒒𝒒𝟑𝟑} δ(𝒒𝒒𝟐𝟐,𝟎𝟎) =
δ(𝒒𝒒𝟏𝟏,𝜺𝜺) =
1/29/2020 CS332 – Theory of Computation 9
Nondeterminism
Deterministic Computation
Nondeterministic Computation
Ways to think about nondeterminism
• (restricted) parallel computation
• tree of possible computations
• guessing and verifying the “right” choice
reject
accept or reject
accept
1/29/2020
CS332 – Theory of Computation 10
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
language {1}:
An NFA that recognizes the language {1}:
1
A DFA that recognizes the
0,1
0 1
0,1
1/29/2020 CS332 – Theory of Computation
12
Sometimes DFAs must be larger
Theorem. Every DFA for the language {1} 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
Let𝑁𝑁 = (𝑄𝑄,Σ,δ,𝑞𝑞 ,𝐹𝐹)beanNFA
Equivalence of NFAs and DFAs (Proof)
0
Goal:ConstructDFA𝑀𝑀 =(𝑄𝑄′,Σ,δ′,𝑞𝑞0′,𝐹𝐹′)recognizing𝐿𝐿(𝑁𝑁)
Intuition: Run all threads of 𝑁𝑁 in parallel, maintaining the set of states where all threads are.
reject
Formally: 𝑄𝑄𝑄 = 𝑃𝑃(𝑄𝑄)
“The Subset Construction”
1/29/2020
CS332 – Theory of Computation 16
accept
NFA -> DFA Example
a
1
b
1/29/2020
CS332 – Theory of Computation
17
Subset Construction (Formally)
Input: NFA 𝑁𝑁 = (𝑄𝑄,Σ,𝛿𝛿,𝑞𝑞0,𝐹𝐹) Output: DFA 𝑀𝑀 = (𝑄𝑄′, Σ, 𝛿𝛿′, 𝑞𝑞0′, 𝐹𝐹′)
𝑄𝑄′
𝛿𝛿′∶ 𝑄𝑄′×Σ → 𝑄𝑄′
𝛿𝛿′ 𝑅𝑅, σ = for all 𝑅𝑅 ⊆ 𝑄𝑄 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 𝑁𝑁 = (𝑄𝑄,Σ,𝛿𝛿,𝑞𝑞0,𝐹𝐹) Output: DFA 𝑀𝑀 = (𝑄𝑄′, Σ, 𝛿𝛿′, 𝑞𝑞0′, 𝐹𝐹′)
𝑄𝑄′ = 𝑃𝑃(𝑄𝑄)
𝛿𝛿′∶ 𝑄𝑄′×Σ → 𝑄𝑄′
𝛿𝛿′ 𝑅𝑅, σ = ⋃𝑟𝑟∈𝑅𝑅 𝛿𝛿(𝑟𝑟, 𝜎𝜎) for all 𝑅𝑅 ⊆ 𝑄𝑄 and 𝜎𝜎 ∈ Σ. 𝑞𝑞0′ = {𝑞𝑞0}
𝐹𝐹′ ={𝑅𝑅∈𝑄𝑄′|𝑅𝑅containssomeacceptstateof𝑁𝑁} 1/29/2020 CS332 – Theory of Computation 20
Proving the Construction Works
Claim: For every string 𝑤𝑤, running 𝑀𝑀 on 𝑤𝑤 leads to state {𝑞𝑞 ∈ 𝑄𝑄|There exists a computation
of𝑁𝑁oninput𝑤𝑤endingat 𝑞𝑞} 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”
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.
1/29/2020
CS332 – Theory of Computation 22
Is this construction the best we can do?
Subset construction converts an 𝑛𝑛 state NFA into a 2𝑛𝑛-state DFA
Could there be a construction that always produces, say, an 𝑛𝑛2-state DFA?
Theorem: For every 𝑛𝑛 ≥ 1, there is a language 𝐿𝐿𝑛𝑛 such that
1. There is an 𝑛𝑛 + 1 -state NFA recognizing 𝐿𝐿𝑛𝑛.
2. There is no DFA recognizing 𝐿𝐿𝑛𝑛 with fewer than 2𝑛𝑛 states.
Conclusion: For finite automata, nondeterminism provides an exponential savings over determinism (in the worst case).
1/29/2020 CS332 – Theory of Computation 23
More on Closure Properties
1/29/2020 CS332 – Theory of Computation 24
∗
Let 𝐴𝐴, 𝐵𝐵 ⊆{Σ be languages. Define
Operations on languages
Regular Operations
Union: 𝐴𝐴 ∪ 𝐵𝐵
Concatenation:𝐴𝐴 ∘𝐵𝐵= 𝑎𝑎𝑎𝑎 𝑎𝑎∈𝐴𝐴,𝑎𝑎∈𝐵𝐵} Star:𝐴𝐴∗ ={𝑎𝑎1𝑎𝑎2…𝑎𝑎𝑛𝑛|𝑛𝑛 ≥0and𝑎𝑎𝑖𝑖 ∈𝐴𝐴}
Complement: 𝐴𝐴̅
Intersection: 𝐴𝐴 ∩ 𝐵𝐵
Reverse: 𝐴𝐴𝑅𝑅 = { 𝑎𝑎1𝑎𝑎2…𝑎𝑎𝑛𝑛|𝑎𝑎𝑛𝑛…𝑎𝑎1 ∈ 𝐴𝐴}
Theorem: The class of regular languages is closed under all six of these operations
1/29/2020 CS332 – Theory of Computation 25
Closure under Reverse
Theorem. The reverse of a regular language is also regular
Proof: Let 𝐿𝐿 be a regular language and 𝑀𝑀 be a DFA recognizing it.
Construct an NFA 𝑀𝑀′ recognizing 𝐿𝐿𝑅𝑅:
• Define 𝑀𝑀𝑀 as 𝑀𝑀 with the arrows reversed.
• Make the start state of 𝑀𝑀 be the accept state in 𝑀𝑀𝑀.
ε
ε
ε
• Make a new start state that goes to all accept states of 𝑀𝑀 by ε-transitions.
1/29/2020 CS332 – Theory of Computation
26
Closure under Concatenation
Concatenation:𝐴𝐴∘𝐵𝐵 = {𝑎𝑎𝑎𝑎|𝑎𝑎∈𝐴𝐴and𝑎𝑎∈𝐵𝐵}
Theorem. If 𝐴𝐴 and 𝐵𝐵 are regular, 𝐴𝐴 ∘ 𝐵𝐵 is also regular.
Proof: Given DFAs 𝑀𝑀𝐴𝐴 and 𝑀𝑀𝐵𝐵, construct NFA by
• Connecting all accept states in 𝑀𝑀𝐴𝐴 to the start state in 𝑀𝑀𝐵𝐵. • Make all states in 𝑀𝑀𝐴𝐴 non-accepting.
ε 𝐿𝐿(𝑀𝑀𝐵𝐵) = 𝐵𝐵
1/29/2020 CS332 – Theory of Computation 27
𝐿𝐿(𝑀𝑀𝐴𝐴) = 𝐴𝐴
A Mystery Construction
Given DFAs 𝑀𝑀𝐴𝐴 recognizing 𝐴𝐴 and 𝑀𝑀𝐵𝐵 recognizing 𝐵𝐵, what does the following NFA recognize?
ε ε
𝐿𝐿(𝑀𝑀𝐴𝐴) = 𝐴𝐴
𝐿𝐿(𝑀𝑀𝐵𝐵) = 𝐵𝐵
1/29/2020
CS332 – Theory of Computation 28
Closure under Star
Star:𝐴𝐴∗ ={𝑎𝑎1𝑎𝑎2…𝑎𝑎𝑛𝑛|𝑛𝑛 ≥0and𝑎𝑎𝑖𝑖 ∈𝐴𝐴} Theorem. If 𝐴𝐴 is regular, 𝐴𝐴∗ is also regular.
𝐿𝐿(𝑀𝑀) = 𝐴𝐴
1/29/2020 CS332 – Theory of Computation 29