Microsoft PowerPoint – CS332-Lec03
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 (ON / OFF)
• = Units button (cycles through g / oz / lb)
Only works when scale is ON, but units remembered when scale
is OFF
• Starts OFF in gmode
• A computational problem: Does a sequence of button
presses in ∗ leave the scale ON in ozmode?
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
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/
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
∗ (where each ) if there exist
, . . . , such that
1.
2. for each and
3.
Example: Computing with the Parity DFA
2/1/2021 CS332 ‐ Theory of Computation 15
0 1
A DFA 0 accepts a string
∗ (where each ) if there exist
, . . . , such that
1.
2. for each and
3.
Let 𝑤 𝑎𝑏𝑏𝑎
Does 𝑀 accept 𝑤?
What is 𝛿 𝑟 ,𝑤 ?
a) 𝑞
b) 𝑞
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