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

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