# 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