PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 3:
• Deterministic Finite
Automata
• Non-deterministic FAs
Reading:
Sipser Ch 1.1-1.2
Mark Bun
February 1, 2021
Last Time
• Parts of a theory of computation: Model for machines,
model for problems, theorems relating machines and
problems
• Strings: Finite concatenations of symbols
• Languages: Sets 𝐿 of strings
• Computational (decision) problem: Given a string 𝑥, is it
in the language 𝐿?
2/1/2021 CS332 – Theory of Computation 2
Deterministic Finite
Automata
2/1/2021 CS332 – Theory of Computation 3
A (Real-Life?) Example
• Example: Kitchen scale
• 𝑃 = Power button ( / )
• 𝑈 = Units button (cycles through / / )
Only works when scale is , but units remembered when scale
is
• Starts in mode
• A computational problem: Does a sequence of button
presses in {𝑃, 𝑈}∗ leave the scale in mode?
2/1/2021 CS332 – Theory of Computation 4
Machine Models
• Finite Automata (FAs): Machine with a finite amount of
unstructured memory
2/1/2021 CS332 – Theory of Computation 5
Input 𝑃 𝑈 𝑃 𝑈
Finite
control
…
Control scans left-to-right
A DFA for the Kitchen Scale Problem
2/1/2021 CS332 – Theory of Computation 6
A DFA Recognizing Parity
The language recognized by a DFA is the set of inputs on
which it ends in an “accept” state
Parity: Given a string consisting of 𝑎’s and 𝑏’s, does
it contain an even number of 𝑎’s?
Ʃ = {𝑎, 𝑏} 𝐿 = {𝑤 | 𝑤 contains an even number of 𝑎’s}
2/1/2021 CS332 – Theory of Computation 7
Which state is reached by the
parity DFA on input aabab?
a) “even”
b) “odd”
Anatomy of a DFA
2/1/2021 CS332 – Theory of Computation 8
𝒒𝟐
0
0,1
00
1
1
1
𝒒𝟎
𝒒𝟏
𝒒𝟑
Some Tips for Thinking about DFAs
Given a DFA, what language does it recognize?
– Try experimenting with it on short strings. Do you notice
any patterns?
– What kinds of inputs cause the DFA to get trapped in a
state?
Given a language, construct a DFA recognizing it
– Imagine you are a machine, reading one symbol at a
time, always prepared with an answer
– What is the essential information that you need to
remember? Determines set of states.
2/1/2021 CS332 – Theory of Computation 9
What language does this DFA recognize?
2/1/2021 CS332 – Theory of Computation 10
1 0
1
0 0 1
0,1
𝑞0 𝑞1 𝑞2 𝑞3
Practice!
2/1/2021 CS332 – Theory of Computation 11
• Lots of worked out examples in Sipser
• Tomorrow’s discussion section
• Automata Tutor: https://automata-
tutor.model.in.tum.de/
https://automata-tutor.model.in.tum.de/
Formal Definition of a DFA
2/1/2021 CS332 – Theory of Computation 12
𝑄 is the set of states
Σ is the alphabet
𝛿: 𝑄 × Σ → 𝑄 is the transition function
𝑞0 𝑄 is the start state
𝐹 ⊆ 𝑄 is the set of accept states
A finite automaton is a 5-tuple 𝑀 = (𝑄, Σ,𝛿, 𝑞0, 𝐹)
A DFA for Parity
Parity: Given a string consisting of 𝑎’s and 𝑏’s, does
it contain an even number of 𝑎’s?
Ʃ = {𝑎, 𝑏} 𝐿 = {𝑤 | 𝑤 contains an even number of 𝑎’s}
2/1/2021 CS332 – Theory of Computation 13
𝑞0 𝑞1
𝑏 𝑏
𝑎
𝑎
State set 𝑄 =
Alphabet Ʃ =
Transition function 𝛿
Start state 𝑞0
Set of accept states 𝐹 =
𝛿 𝑎 𝑏
𝑞0
𝑞1
Formal Definition of DFA Computation
2/1/2021 CS332 – Theory of Computation 14
𝐿(𝑀) = the language of machine 𝑀
= set of all strings machine 𝑀 accepts
𝑀 recognizes the language 𝐿(𝑀)
A DFA 𝑀 = (𝑄, Σ, 𝛿, 𝑞0, 𝐹) accepts a string
𝑤 = 𝑤1𝑤2 · · · 𝑤𝑛 ∈ Σ
∗ (where each 𝑤𝑖 ∈ Σ) if there exist
𝑟0, . . . , 𝑟𝑛 ∈ 𝑄 such that
1. 𝑟0 = 𝑞0
2. 𝛿(𝑟𝑖 , 𝑤𝑖+1) = 𝑟𝑖+1 for each 𝑖 = 0, . . . , 𝑛 − 1, and
3. 𝑟𝑛 ∈ 𝐹
Example: Computing with the Parity DFA
2/1/2021 CS332 – Theory of Computation 15
𝑞0 𝑞1
𝑏 𝑏
𝑎
𝑎
A DFA 𝑀 = (𝑄, Σ, , 𝑞0, 𝐹) accepts a string
𝑤 = 𝑤1𝑤2 · · · 𝑤𝑛 ∈ Σ
∗ (where each 𝑤𝑖 ∈ Σ) if there exist
𝑟0, . . . , 𝑟𝑛 ∈ 𝑄 such that
1. 𝑟0 = 𝑞0
2. 𝛿(𝑟𝑖 , 𝑤𝑖+1) = 𝑟𝑖+1 for each 𝑖 = 0, . . . , 𝑛 − 1, and
3. 𝑟𝑛 ∈ 𝐹
Let 𝑤 = 𝑎𝑏𝑏𝑎
Does 𝑀 accept 𝑤?
What is 𝛿 𝑟2, 𝑤3 ?
a) 𝑞0
b) 𝑞1
Regular Languages
2/1/2021 CS332 – Theory of Computation 16
Definition: A language is regular if it is recognized by a DFA
𝑳 = { 𝒘 ∈ 𝟎, 𝟏 ∗| 𝒘 contains 𝟎𝟎𝟏 } is regular
𝑳 = { 𝒘 ∈ 𝒂, 𝒃 ∗ | 𝒘 has an even number of 𝒂’s } is regular
Many interesting programs recognize regular languages
NETWORK PROTOCOLS
COMPILERS
GENETIC TESTING
ARITHMETIC
Internet Transmission Control Protocol
2/1/2021 CS332 – Theory of Computation 17
Let TCPS = { 𝑤 | 𝑤 is a complete TCP Session}
Theorem. TCPS is regular
Compilers
2/1/2021 CS332 – Theory of Computation 18
Comments :
Are delimited by /* */
Cannot have nested /* */
Must be closed by */
*/ is illegal outside a comment
COMMENTS = {strings over {0,1, /, *} with legal comments}
Theorem. COMMENTS is regular.
Genetic Testing
2/1/2021 CS332 – Theory of Computation 19
DNA sequences are strings over the alphabet {𝑨, 𝑪, 𝑮, 𝑻}.
A gene 𝒈 is a special substring over this alphabet.
A genetic test searches a DNA sequence for a gene.
GENETICTEST𝒈 = {strings over {𝑨, 𝑪, 𝑮, 𝑻} containing 𝒈 as a substring}
Theorem. GENETICTEST𝒈 is regular for every gene 𝒈.
Arithmetic
2/1/2021 CS332 – Theory of Computation 20
LET =
• A string over has three ROWS (ROW1, ROW2, ROW3)
• Each ROW 𝒃𝟎𝒃𝟏𝒃𝟐…𝒃𝑵 represents the integer
𝒃𝟎 + 𝟐𝒃𝟏 + … + 𝟐
𝑵𝒃𝑵.
• Let ADD = {𝑺 ∈ 𝚺∗| ROW1 + ROW2 = ROW3 }
Theorem. ADD is regular.
{ [ ],[ ],[ ],[ ],
[ ],[ ],[ ],[ ]}
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
Nondeterministic Finite
Automata
2/1/2021 CS332 – Theory of Computation 21
Nondeterminism
2/1/2021 CS332 – Theory of Computation 22
In a DFA, the machine is always in exactly one state upon
reading each input symbol
In a nondeterministic FA, the machine can try out many
different ways of reading the same string
– Next symbol may cause an NFA to “branch” into
multiple possible computations
– Next symbol may cause NFA’s computation to fail to
enter any state at all
Nondeterminism
2/1/2021 CS332 – Theory of Computation 23
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.
Nondeterminism
2/1/2021 CS332 – Theory of Computation 24
1 0
1
0
1
0,1
0
Example: Does this NFA accept the string 1100?
Some special transitions
2/1/2021 CS332 – Theory of Computation 25
0
0, 1
𝜺
1
Example
2/1/2021 CS332 – Theory of Computation 26
1
0
0
𝑳(𝑴) =
𝜺
𝜺
0,1
Example
2/1/2021 CS332 – Theory of Computation 27
0,1
0,𝜺 1
0,1
1
Now You Try!
2/1/2021 CS332 – Theory of Computation 28
0
0
0
ε
ε
0
0
What is the language of this NFA? (over alphabet {0})
a) {0𝑘 | 𝑘 is a multiple of 2}
b) {0𝑘 | 𝑘 is a multiple of 3}
c) {0𝑘 | 𝑘 is a multiple of 6}
d) 0𝑘 𝑘 is a multiple of 2 or a multiple of 3}
Formal Definition of a NFA
2/1/2021 CS332 – Theory of Computation 29
𝑄 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/1/2021 CS332 – Theory of Computation 30
1
0
0
𝜺
𝜺
𝜹(𝒒𝟑, 𝟏) =
𝑴 = (𝑸, 𝚺, 𝜹, 𝑸𝟎, 𝑭)
𝑸 = {𝒒𝟎,
𝒒𝟏, 𝒒𝟐, 𝒒𝟑, 𝒒𝟒}
𝚺 = {𝟎, 𝟏}
𝑭 = {𝒒𝟒}
𝜹(𝒒𝟐, 𝟏) =
𝒒𝟏
𝒒𝟐
𝒒𝟑
𝒒𝟒
𝒒𝟎
Example
2/1/2021 CS332 – Theory of Computation 31
0,1
0,𝜺 1
0,1
1
𝒒𝟏 𝒒𝟐 𝒒𝟑𝒒𝟎
𝑵 = (𝑸, 𝚺, , 𝒒𝟎, 𝑭)
𝑸 = {𝒒𝟎,
𝒒𝟏, 𝒒𝟐, 𝒒𝟑}
𝚺 = {𝟎, 𝟏}
𝑭 = {𝒒𝟑}
(𝒒𝟎, 𝟏) =
(𝒒𝟐, 𝟎) =
(𝒒𝟎, 𝟎) =
(𝒒𝟏, 𝜺) =
Nondeterminism
2/1/2021 CS332 – Theory of Computation 32
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 actually 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/1/2021 CS332 – Theory of Computation 33