PowerPoint Presentation
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) 𝑤 𝑤 contains 00 or 01}
b) 𝑤 the second to last symbol of 𝑤 is 0}
c) 𝑤 𝑤 starts with 00 or 01}
d) 𝑤 𝑤 ends with 001}
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,1
0
A DFA that recognizes the language
𝑤 𝑤 starts with 0 and ends with 1}:
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) 𝑠2
c) 2𝑠
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 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).
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 ℤ = {…− 2,−1, 0, 1, 2, … } 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
Proving Closure Properties
2/3/2021 CS332 – Theory of Computation 27
Complement
Complement: ҧ𝐴 = 𝑤 𝑤 ∉ 𝐴}
Theorem: If 𝐴 is regular, then ҧ𝐴 is also regular
Proof idea:
2/3/2021 CS332 – Theory of Computation 28
Complement, Formally
Let 𝑀 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹) be a DFA recognizing a language
𝐴. Which of the following represents a DFA recognizing ҧ𝐴?
a) (𝐹, Σ, 𝛿, 𝑞0, 𝑄)
b) (𝑄, Σ, 𝛿, 𝑞0, 𝑄 ∖ 𝐹), where 𝑄 ∖ 𝐹 is the set of states in
𝑄 that are not in 𝐹
c) (𝑄, Σ, 𝛿′, 𝑞0, 𝐹) where 𝛿′(𝑞, 𝑠) = 𝑝 such that
𝛿(𝑝, 𝑠) = 𝑞
d) None of the above
2/3/2021 CS332 – Theory of Computation 29
Closure under Concatenation
2/3/2021 CS332 – Theory of Computation 30
Concatenation: 𝐴 ∘ 𝐵 = 𝑥𝑦 𝑥 𝐴, 𝑦 𝐵 }
Theorem. If 𝐴 and 𝐵 are regular, 𝐴 ∘ 𝐵 is also regular.
Proof idea: Given DFAs 𝑀𝐴 and 𝑀𝐵, construct NFA by
• Connecting all accept states in 𝑀𝐴 to the start state in 𝑀𝐵.
• Make all states in 𝑀𝐴 non-accepting.
𝐿(𝑀𝐴) = 𝐴 𝐿(𝑀𝐵) = 𝐵
Closure under Concatenation
2/3/2021 CS332 – Theory of Computation 31
Concatenation: 𝐴 ∘ 𝐵 = 𝑥𝑦 𝑥 𝐴, 𝑦 𝐵 }
Theorem. If 𝐴 and 𝐵 are regular, 𝐴 ∘ 𝐵 is also regular.
Proof idea: Given DFAs 𝑀𝐴 and 𝑀𝐵, construct NFA by
• Connecting all accept states in 𝑀𝐴 to the start state in 𝑀𝐵.
• Make all states in 𝑀𝐴 non-accepting.
ε
ε
𝐿(𝑀𝐴) = 𝐴 𝐿(𝑀𝐵) = 𝐵
A Mystery Construction
2/3/2021 CS332 – Theory of Computation 32
ε
ε
𝐿(𝑀𝐴) = 𝐴
𝐿(𝑀𝐵) = 𝐵
Given DFAs 𝑀𝐴 recognizing 𝐴 and 𝑀𝐵 recognizing 𝐵, what does the
following NFA recognize?
Closure under Star
2/3/2021 CS332 – Theory of Computation 33
Star: 𝐴∗ = { 𝑎1𝑎2…𝑎𝑛|𝑛 ≥ 0 and 𝑎𝑖 ∈ 𝐴}
Theorem. If 𝐴 is regular, 𝐴∗ is also regular.
𝐿(𝑀) = 𝐴
Closure under Star
2/3/2021 CS332 – Theory of Computation 34
Star: 𝐴∗ = { 𝑎1𝑎2…𝑎𝑛|𝑛 ≥ 0 and 𝑎𝑖 ∈ 𝐴}
Theorem. If 𝐴 is regular, 𝐴∗ is also regular.
𝐿(𝑀) = 𝐴
ε
ε
ε
On proving your own closure properties
You’ll have homework/test problems of the form “show
that the regular languages are closed under operation op”
What would Sipser do?
– Give the “proof idea”: Explain how to take machine(s)
recognizing regular language(s) and create a new
machine
– Explain in a few sentences why the construction works
– Give a formal description of the construction
– No need to formally prove the construction works
2/3/2021 CS332 – Theory of Computation 35