CS代考计算机代写 DNA compiler BU CS 332 – Theory of Computation

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