BU CS 332 – Theory of Computation
Lecture 2:
• Deterministic Finite Automata
Reading:
Sipser Ch 1.1‐1.2
• Regular Operations
• Non‐deterministic FAs
Mark Bun January 27, 2020
Deterministic Finite Automata
1/29/2020 CS332 ‐ Theory of Computation 2
A (Real‐Life?) Example
• Example: Car stereo
• = Power button (ON/OFF)
• = Source button (cycles through Radio/Bluetooth/USB) Only works when stereo is ON, but source remembered when
stereo is OFF
• Starts OFF in Radio mode
• A computational problem: Does a sequence of button presses in ∗ leave the stereo ON in USB mode?
1/29/2020 CS332 ‐ Theory of Computation 3
Machine Models
• Finite Automata (FAs): Machine with a finite amount of unstructured memory
Input 𝑃𝑆𝑃𝑆
…
Control scans left‐to‐right
1/29/2020
CS332 ‐ Theory of Computation 4
Finite control
A DFA for the car stereo problem
1/29/2020 CS332 ‐ Theory of Computation 5
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
1/29/2020 CS332 ‐ Theory of Computation 6
Anatomy of a DFA
1/29/2020
CS332 ‐ Theory of Computation
7
0
1
𝒒𝟏
1 0,1
𝒒𝟎
𝒒𝟐
0
0
1
𝒒𝟑
Formal Definition of a DFA
A finite automaton is a 5‐tuple is the set of states
0
is the alphabet
0
is the transition function is the start state
1/29/2020
CS332 ‐ Theory of Computation 8
is the set of accept states
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
1/29/2020
CS332 ‐ Theory of Computation
9
01
𝑞0 𝑞1
State set =
Alphabet =
Transition function
𝛿𝑎𝑏
Start state
Set of accept states
0
=
Formal Definition of DFA Computation
A DFA
0 ∗ accepts a string (where each
,…,
suchthat
for each
1. 2. 3.
and
) if there exist
= the language of machine
= set of all (finite) strings machine
accepts
recognizes the language
1/29/2020 CS332 ‐ Theory of Computation
10
Example: Computing with the Parity DFA
A DFA
accepts a string (where each
,…,
1.
2.
for each
CS332 ‐ Theory of Computation
and
3.
1/29/2020
11
01
) if there exist
0 ∗ suchthat
Let𝑤 𝑎𝑏𝑏𝑎 Does 𝑀 accept 𝑤?
Automata Tutor
http://automatatutor.com/
1/29/2020 CS332 ‐ Theory of Computation 12
Regular Languages
Definition: A language is regular if it is recognized by a DFA 𝑳={𝒘 ∈ 𝒂,𝒃 ∗ |𝒘hasanevennumberof𝒂’s}isregular
𝑳={𝒘 ∈ 𝟎,𝟏 ∗|𝒘contains𝟎𝟎𝟏}isregular
Many interesting programs recognize regular languages
NETWORK PROTOCOLS COMPILERS GENETIC TESTING ARITHMETIC
1/29/2020 CS332 ‐ Theory of Computation 13
Internet Transmission Control Protocol
Let TCPS = { | is a complete TCP Session} Theorem. TCPS is regular
1/29/2020 CS332 ‐ Theory of Computation 14
Compilers
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.
1/29/2020 CS332 ‐ Theory of Computation 15
Genetic Testing
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 𝒈.
1/29/2020 CS332 ‐ Theory of Computation 16
Arithmetic
{ [0 ],[01 ],[010 ],[01 ],
LET 3 =
[1],[1],[1],[1]}
0011 0101
• A string over 3 has three ROWS (ROW1, ROW2, ROW3) • Each ROW 𝟎 𝟏 𝟐 𝑵 represents the integer
𝟎 𝟏 𝑵𝑵. •LetADD={ 𝟑∗|ROW1 +ROW2 =ROW3}
Theorem. ADD is regular.
1/29/2020 CS332 ‐ Theory of Computation 17
Regular Operations
1/29/2020 CS332 ‐ Theory of Computation 18
An Analogy
In algebra, we try to identify operations which are common to many different mathematical structures
Example: The integers are closed under
• Addition:
• Multiplication: ×
• Negation:
• …but NOT Division:
We’d like to investigate similar closure properties of the
class of regular languages
1/29/2020 CS332 ‐ Theory of Computation 19
Regular operations on languages
Let ∗ be languages. Define Union:
Concatenation:
Star:
∗
1/29/2020 CS332 ‐ Theory of Computation 20
Other operations
Let ∗ be languages. Define Complement:
Intersection:
Reverse:
1/29/2020
CS332 ‐ Theory of Computation 21
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
1/29/2020 CS332 ‐ Theory of Computation 22
Proving Closure Properties
1/29/2020 CS332 ‐ Theory of Computation 23
Complement
Complement:
Theorem: If is regular, then is also regular Proof idea:
1/29/2020 CS332 ‐ Theory of Computation 24
Union
Union: or
Theorem: If Proof:
and are regular, then so is
Let 𝐴 𝐵
𝐴 𝐴 𝐴 𝐵 𝐵 𝐵
be a DFA recognizing and be a DFA recognizing
Goal: Construct a DFA that recognizes
1/29/2020
CS332 ‐ Theory of Computation
25
Example
1/29/2020
CS332 ‐ Theory of Computation
26
0
0
1
1
?
0
1
1
𝑨
0
𝑩
Closure under union proof (cont’d)
Idea: Run both 𝐴 and 𝐵 at the same time “Cross‐product construction”
𝐴×𝐵
,
𝐴𝐵 𝐴𝐴𝐵𝐵
, 𝐴 𝐵
𝐴×𝐵 𝐴×𝐵
1/29/2020 CS332 ‐ Theory of Computation 27
Example (cont’d)
0
0
1
1
𝑨 1
1
𝑩 0
0 1/29/2020
CS332 ‐ Theory of Computation 28
Intersection
Intersection: and
Theorem: If Proof:
and are regular, then so is
Let 𝐴 𝐵
𝐴 𝐴 𝐴 𝐵 𝐵 𝐵
be a DFA recognizing and be a DFA recognizing
Goal: Construct a DFA that recognizes
1/29/2020
CS332 ‐ Theory of Computation
29
Intersection
Intersection:
and are regular, then so is
Theorem: If and Another Proof:
1/29/2020
CS332 ‐ Theory of Computation 30
=
Reverse
Reverse:
is regular, then is also regular
Theorem: If Proof idea:
Goal: Construct a DFA
be a DFA recognizing
Let
that recognizes
Define as but
• With the arrows reversed
• With start and accept states swapped
1/29/2020 CS332 ‐ Theory of Computation 31
Example (Reverse)
𝑴
0 1
𝑴′
1/29/2020
CS332 ‐ Theory of Computation 32
1
0,1 01
0
Closure under reverse
is not always a DFA! • It might have many start states
• Some states may have too many outgoing edges, or none at all
1/29/2020 CS332 ‐ Theory of Computation 33
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 34
0