BU CS 332 – Theory of Computation
Lecture 2:
• Deterministic Finite Automata
• Regular Operations
• Non-deterministic FAs
Mark Bun January 27, 2020
Reading:
Sipser Ch 1.1-1.2
Deterministic Finite Automata
1/26/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/26/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/26/2020
CS332 – Theory of Computation 4
Finite control
A DFA for the car stereo problem
1/26/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/26/2020 CS332 – Theory of Computation 6
Anatomy of a DFA
0
1
𝒒𝟎
𝒒𝟏
1 0,1
𝒒𝟐
0
𝒒𝟑
0
1
1/26/2020
CS332 – Theory of Computation
7
Formal Definition of a DFA
A finite automaton is a 5-tuple 𝑀 = (𝑄, Σ, , 𝑞0, 𝐹) 𝑄 is the set of states
Σ is the alphabet
∶ 𝑄 × Σ → 𝑄 is the transition function 𝑞0 𝑄 is the start state
𝐹 ⊆ 𝑄 is the set of accept states
1/26/2020 CS332 – Theory of Computation 8
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}
𝑏
State set 𝑄 =
Alphabet Ʃ =
Transition function 𝛿 𝛿𝑎𝑏
𝑞0 𝑞1
Start state 𝑞0
Set of accept states 𝐹 =
𝑞𝑎𝑞 0𝑎1
1/26/2020
CS332 – Theory of Computation 9
Formal Definition of DFA Computation
A DFA 𝑀 = (𝑄,Σ,,𝑞0,𝐹) accepts a string
𝑤 = 𝑤 𝑤 · · · 𝑤 ∈ Σ∗ (where each 𝑤 ∈ Σ) if there exist
12𝑛𝑖
𝑟 , . . . , 𝑟 ∈ 𝑄 such that 0𝑛
1. 𝑟 =𝑞 00
2. 𝛿(𝑟,𝑤 ) =𝑟 foreach𝑖= 0,…,𝑛−1,and 𝑖 𝑖+1 𝑖+1
3. 𝑟 ∈ 𝐹 𝑛
𝐿(𝑀) = the language of machine 𝑀
= set of all (finite) strings machine 𝑀 accepts
𝑀 recognizes the language 𝐿(𝑀)
1/26/2020 CS332 – Theory of Computation 10
Example: Computing with the Parity DFA
𝑏
Let 𝑤 = 𝑎𝑏𝑏𝑎 Does 𝑀 accept 𝑤?
𝑏 𝑞𝑎𝑞
0𝑎1
A DFA 𝑀 = (𝑄,Σ,,𝑞0,𝐹) accepts a string
𝑤 = 𝑤 𝑤 · · · 𝑤 ∈ Σ∗ (where each 𝑤 ∈ Σ) if there exist 12𝑛𝑖
𝑟 , . . . , 𝑟 ∈ 𝑄 such that 0𝑛
1. 𝑟 =𝑞 00
2. 𝛿(𝑟,𝑤 ) =𝑟 foreach𝑖= 0,…,𝑛−1,and 𝑖 𝑖+1 𝑖+1
3. 𝑟 ∈ 𝐹 𝑛
1/26/2020 CS332 – Theory of Computation 11
Automata Tutor
http://automatatutor.com/
1/26/2020 CS332 – Theory of Computation 12
Regular Languages
Definition: A language is regular if it is recognized by a DFA 𝑳 = { 𝒘 ∈ 𝒂, 𝒃 ∗ | 𝒘 has an even number of 𝒂’s } is regular
𝑳 = { 𝒘 ∈ 𝟎, 𝟏 ∗| 𝒘 contains 𝟎𝟎𝟏 } is regular
Many interesting programs recognize regular languages
NETWORK PROTOCOLS COMPILERS GENETIC TESTING ARITHMETIC
1/26/2020 CS332 – Theory of Computation 13
Internet Transmission Control Protocol
Let TCPS = { 𝑤 | 𝑤 is a complete TCP Session} Theorem. TCPS is regular
1/26/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/26/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/26/2020 CS332 – Theory of Computation 16
Arithmetic
0011
{ [0 ],[0 ],[0 ],[0 ],
LET 3 =
[1 ],[1 ],[1 ],[1 ]}
0101
0011 0101
• A string over 3 has three ROWS (ROW1, ROW2, ROW3) • Each ROW 𝒃𝟎𝒃𝟏𝒃𝟐 … 𝒃𝑵 represents the integer
𝒃𝟎 +𝟐𝒃𝟏 +…+𝟐𝑵𝒃𝑵. • Let ADD = {𝑺 ∈ 𝟑∗ | ROW1 + ROW2 = ROW3 }
Theorem. ADD is regular.
1/26/2020 CS332 – Theory of Computation
17
Regular Operations
1/26/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 Z = {… − 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
1/26/2020 CS332 – Theory of Computation 19
Regular operations on languages
Let 𝐴, 𝐵 ⊆ Σ∗ be languages. Define Union:𝐴 ∪𝐵=
Concatenation: 𝐴 ∘ 𝐵 =
Star: 𝐴∗ =
1/26/2020 CS332 – Theory of Computation 20
Other operations
Let 𝐴, 𝐵 ⊆ Σ∗ be languages. Define Complement: 𝐴ҧ =
Intersection: 𝐴 ∩ 𝐵 =
Reverse: 𝐴𝑅 =
1/26/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/26/2020 CS332 – Theory of Computation 22
Proving Closure Properties
1/26/2020 CS332 – Theory of Computation 23
Complement
Complement: 𝐴ҧ = 𝑤 𝑤 ∉ 𝐴}
Theorem: If 𝐴 is regular, then 𝐴ҧ is also regular Proof idea:
1/26/2020 CS332 – Theory of Computation 24
Union
Union:𝐴∪𝐵= 𝑤 𝑤∈𝐴 or 𝑤∈𝐵} Theorem: If 𝐴 and 𝐵 are regular, then so is 𝐴 ∪ 𝐵 Proof:
Let 𝑀 = (𝑄 ,Σ, ,𝑞𝐴,𝐹 ) be a DFA recognizing 𝐴 and 𝐴𝐴𝐴0𝐴
𝑀 = (𝑄 ,Σ, ,𝑞𝐵,𝐹 ) be a DFA recognizing 𝐵 𝐵𝐵𝐵0𝐵
Goal: Construct a DFA 𝑀 = 𝑄, Σ, , 𝑞0, 𝐹 that recognizes 𝐴 ∪ 𝐵
1/26/2020 CS332 – Theory of Computation 25
Example
0
0
𝑴𝑨
1
𝑞𝐴 01
𝑞𝐴
1
1
1
𝑴=? 1/26/2020
𝑴𝑩
0
𝑞𝐵 01
0
𝑞𝐵
CS332 – Theory of Computation
26
Closure under union proof (cont’d)
Idea: Run both 𝑀𝐴 and 𝑀𝐵 at the same time “Cross-product construction”
𝑄 = 𝑄𝐴 × 𝑄𝐵
= {(𝑞𝐴,𝑞𝐵)|𝑞𝐴 ∈𝐴 and 𝑞𝐵 ∈𝐵}
((𝑞𝐴,𝑞𝐵),) = (𝐴(𝑞𝐴,),𝐵(𝑞𝐵,)) 𝑞 =(𝑞𝐴,𝑞𝐵)
000
𝐹 = {(𝑞𝐴,𝑞𝐵)|𝑞𝐴 ∈𝐹𝐴 or 𝑞𝐵 ∈𝐹𝐵}
=𝐹𝐴 ×𝑄𝐵 ∪𝑄𝐴 ×𝐹𝐵
1/26/2020 CS332 – Theory of Computation 27
Example (cont’d)
0
011
𝑴
0 𝑞𝐴 1 𝑞𝐴
𝑴𝑨
1
1
𝑴𝑩
𝑞𝐵 0 𝑞𝐵
001 1/26/2020
CS332 – Theory of Computation
28
Intersection
Intersection:𝐴 ∩𝐵= 𝑤 𝑤∈𝐴 and 𝑤∈𝐵} Theorem: If 𝐴 and 𝐵 are regular, then so is 𝐴 ∩ 𝐵 Proof:
Let 𝑀 = (𝑄 ,Σ, ,𝑞𝐴,𝐹 ) be a DFA recognizing 𝐴 and 𝐴𝐴𝐴0𝐴
𝑀 = (𝑄 ,Σ, ,𝑞𝐵,𝐹 ) be a DFA recognizing 𝐵 𝐵𝐵𝐵0𝐵
Goal: Construct a DFA 𝑀 = 𝑄, Σ, , 𝑞0, 𝐹 that recognizes 𝐴 ∩ 𝐵
1/26/2020 CS332 – Theory of Computation 29
Intersection
Intersection:𝐴 ∩𝐵= 𝑤 𝑤∈𝐴 and 𝑤∈𝐵} Theorem: If 𝐴 and 𝐵 are regular, then so is 𝐴 ∩ 𝐵 Another Proof:
ҧത 𝐴∩𝐵=𝐴∪𝐵
1/26/2020 CS332 – Theory of Computation 30
Reverse
Reverse:𝐴𝑅 = 𝑤 𝑤 ···𝑤 𝑤 ···𝑤 ∈𝐴} 12𝑛𝑛1
Theorem: If 𝐴 is regular, then 𝐴𝑅 is also regular Proof idea:
Let 𝑀 = (𝑄,Σ,,𝑞0,𝐹) be a DFA recognizing 𝐴 Goal: Construct a DFA 𝑀′ = 𝑄′, Σ, ′, 𝑞′ , 𝐹′
that recognizes 𝐴𝑅
Define 𝑀′ as 𝑀 but
• With the arrows reversed
• With start and accept states swapped
1/26/2020 CS332 – Theory of Computation 31
0
Example (Reverse)
1
0
1
0
01
0,1
𝑴
𝑴′
1/26/2020
CS332 – Theory of Computation 32
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/26/2020 CS332 – Theory of Computation 33
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/26/2020 CS332 – Theory of Computation 34
Example
𝜺
1
0
1/26/2020
CS332 – Theory of Computation
35
𝜺
0
𝑳(𝑴) =
Example
0,1
0,1
1 0,𝜺 1
𝑳(𝑴) =
1/26/2020
CS332 – Theory of Computation
36
Formal Definition of a NFA
An NFA is a 5-tuple 𝑀 = (𝑄, Σ, , 𝑞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 𝑞0 to
an accept state that can be followed by reading 𝑤. 1/26/2020 CS332 – Theory of Computation 37
Example
𝒒𝟐
𝜺
1
𝒒𝟒
0
𝒒𝟎
𝒒
𝑴 = (𝑸,𝚺,,𝑸𝟎,𝑭) 𝑸 = {𝒒𝟎, 𝒒𝟏,𝒒𝟐,𝒒𝟑,𝒒𝟒}
𝚺= {𝟎,𝟏} 𝑭 = {𝒒𝟒}
𝟑
1/26/2020
(𝒒𝟑,𝟏) =
CS332 – Theory of Computation 38
𝜺
0
𝒒𝟏
(𝒒𝟐,𝟏) =
Example
0,1
0,1
𝒒 1 𝒒 0,𝜺 𝒒 1 𝒒 𝟎𝟏𝟐𝟑
𝑵 = (𝑸,𝚺,,𝒒𝟎,𝑭) 𝑸 = {𝒒𝟎, 𝒒𝟏, 𝒒𝟐, 𝒒𝟑} 𝚺 = {𝟎,𝟏}
(𝒒𝟎,𝟎) = (𝒒𝟎,𝟏) =
(𝒒𝟏,𝜺) = (𝒒𝟐,𝟎) =
𝑭 = {𝒒𝟑}
1/26/2020 CS332 – Theory of Computation 39
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/26/2020
CS332 – Theory of Computation 40