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

BU CS 332 – Theory of Computation

Lecture 3:

• Nondeterminism

• Equivalence of NFAs and DFAs

• More on closure properties

Mark Bun January 29, 2020

Reading:

Sipser Ch 1.1-1.2

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/29/2020 CS332 – Theory of Computation 2

Nondeterminism 1

0 1

0

01

0,1

Example: Does this NFA accept the string 1100?

1/29/2020 CS332 – Theory of Computation

3

Some special transitions

0𝜺𝜺 0, 1

1

1/29/2020

CS332 – Theory of Computation 4

Example

𝜺𝜺 𝜺𝜺

0

1

0

𝑳𝑳(𝑴𝑴) =

1/29/2020

CS332 – Theory of Computation

5

Example

0,1

1 0,𝜺𝜺 1

0,1

𝑳𝑳(𝑴𝑴) =

1/29/2020

CS332 – Theory of Computation

6

AnNFAisa5-tuple𝑀𝑀 = (𝑄𝑄,Σ,δ,𝑞𝑞 ,𝐹𝐹)

Formal Definition of a NFA

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 𝑞𝑞 to 0

an accept state that can be followed by reading 𝑤𝑤. 1/29/2020 CS332 – Theory of Computation 7

Example 𝒒𝒒 𝒒𝒒𝜺𝜺𝟐𝟐1

𝒒𝒒𝟒𝟒

𝟎𝟎 𝒒𝒒 0

𝑴𝑴 = (𝑸𝑸,𝚺𝚺,δ,𝑸𝑸𝟎𝟎,𝑭𝑭) 𝑸𝑸 = {𝒒𝒒𝟎𝟎,𝒒𝒒𝟏𝟏,𝒒𝒒𝟐𝟐,𝒒𝒒𝟑𝟑,𝒒𝒒𝟒𝟒}

𝜺𝜺

𝟑𝟑

δ(𝒒𝒒𝟐𝟐,𝟏𝟏) =

𝒒𝒒𝟏𝟏

0

𝚺𝚺= {𝟎𝟎,𝟏𝟏} 𝑭𝑭 = {𝒒𝒒𝟒𝟒}

1/29/2020

δ(𝒒𝒒𝟑𝟑,𝟏𝟏) =

CS332 – Theory of Computation 8

Example

0,1

𝒒𝒒𝟎𝟎 1 𝒒𝒒𝟏𝟏 0,𝜺𝜺 𝒒𝒒𝟐𝟐 1 𝒒𝒒𝟑𝟑

0,1

𝑵𝑵 = (𝑸𝑸,𝚺𝚺,δ,𝒒𝒒𝟎𝟎,𝑭𝑭) 𝑸𝑸 = {𝒒𝒒𝟎𝟎, 𝒒𝒒𝟏𝟏, 𝒒𝒒𝟐𝟐, 𝒒𝒒𝟑𝟑}

δ(𝒒𝒒𝟎𝟎,𝟎𝟎) = δ(𝒒𝒒𝟎𝟎,𝟏𝟏) =

𝚺𝚺 = {𝟎𝟎,𝟏𝟏}

𝑭𝑭 = {𝒒𝒒𝟑𝟑} δ(𝒒𝒒𝟐𝟐,𝟎𝟎) =

δ(𝒒𝒒𝟏𝟏,𝜺𝜺) =

1/29/2020 CS332 – Theory of Computation 9

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/29/2020

CS332 – Theory of Computation 10

Why study NFAs?

• Not really a realistic model of computation: Real computing devices can’t really try many possibilities in parallel

But:

• Useful tool for understanding power of DFAs/regular languages

• NFAs can be simpler than DFAs

• Lets us study “nondeterminism” as a resource

(cf. P vs. NP)

1/29/2020 CS332 – Theory of Computation 11

NFAs can be simpler than DFAs

language {1}:

An NFA that recognizes the language {1}:

1

A DFA that recognizes the

0,1

0 1

0,1

1/29/2020 CS332 – Theory of Computation

12

Sometimes DFAs must be larger

Theorem. Every DFA for the language {1} must have at

least 3 states.

Proof:

1/29/2020 CS332 – Theory of Computation 13

Equivalence of NFAs and DFAs

1/29/2020 CS332 – Theory of Computation 14

Equivalence of NFAs and DFAs

Every DFA is an NFA, so NFAs are at least as powerful as DFAs

Theorem: For every NFA 𝑁𝑁, there is a DFA 𝑀𝑀 such that 𝐿𝐿𝑀𝑀 =𝐿𝐿(𝑁𝑁)

Corollary: A language is regular if and only if it is recognized by an NFA

1/29/2020 CS332 – Theory of Computation 15

Let𝑁𝑁 = (𝑄𝑄,Σ,δ,𝑞𝑞 ,𝐹𝐹)beanNFA

Equivalence of NFAs and DFAs (Proof)

0

Goal:ConstructDFA𝑀𝑀 =(𝑄𝑄′,Σ,δ′,𝑞𝑞0′,𝐹𝐹′)recognizing𝐿𝐿(𝑁𝑁)

Intuition: Run all threads of 𝑁𝑁 in parallel, maintaining the set of states where all threads are.

reject

Formally: 𝑄𝑄𝑄 = 𝑃𝑃(𝑄𝑄)

“The Subset Construction”

1/29/2020

CS332 – Theory of Computation 16

accept

NFA -> DFA Example

a

1

b

1/29/2020

CS332 – Theory of Computation

17

Subset Construction (Formally)

Input: NFA 𝑁𝑁 = (𝑄𝑄,Σ,𝛿𝛿,𝑞𝑞0,𝐹𝐹) Output: DFA 𝑀𝑀 = (𝑄𝑄′, Σ, 𝛿𝛿′, 𝑞𝑞0′, 𝐹𝐹′)

𝑄𝑄′

𝛿𝛿′∶ 𝑄𝑄′×Σ → 𝑄𝑄′

𝛿𝛿′ 𝑅𝑅, σ = for all 𝑅𝑅 ⊆ 𝑄𝑄 and 𝜎𝜎 ∈ Σ. 𝑞𝑞0′ =

𝐹𝐹′ =

1/29/2020 CS332 – Theory of Computation 18

NFA -> DFA Example 0,1 1ε203

1

1/29/2020 CS332 – Theory of Computation 19

Subset Construction (Formally)

Input: NFA 𝑁𝑁 = (𝑄𝑄,Σ,𝛿𝛿,𝑞𝑞0,𝐹𝐹) Output: DFA 𝑀𝑀 = (𝑄𝑄′, Σ, 𝛿𝛿′, 𝑞𝑞0′, 𝐹𝐹′)

𝑄𝑄′ = 𝑃𝑃(𝑄𝑄)

𝛿𝛿′∶ 𝑄𝑄′×Σ → 𝑄𝑄′

𝛿𝛿′ 𝑅𝑅, σ = ⋃𝑟𝑟∈𝑅𝑅 𝛿𝛿(𝑟𝑟, 𝜎𝜎) for all 𝑅𝑅 ⊆ 𝑄𝑄 and 𝜎𝜎 ∈ Σ. 𝑞𝑞0′ = {𝑞𝑞0}

𝐹𝐹′ ={𝑅𝑅∈𝑄𝑄′|𝑅𝑅containssomeacceptstateof𝑁𝑁} 1/29/2020 CS332 – Theory of Computation 20

Proving the Construction Works

Claim: For every string 𝑤𝑤, running 𝑀𝑀 on 𝑤𝑤 leads to state {𝑞𝑞 ∈ 𝑄𝑄|There exists a computation

of𝑁𝑁oninput𝑤𝑤endingat 𝑞𝑞} Proof idea: By induction on |𝑤𝑤|

1/29/2020 CS332 – Theory of Computation 21

Historical Note

Subset Construction introduced in Rabin & Scott’s 1959 paper “Finite Automata and their Decision Problems”

1976 ACM Turing Award citation

For their joint paper “Finite Automata and Their Decision Problem,” which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.

1/29/2020

CS332 – Theory of Computation 22

Is this construction the best we can do?

Subset construction converts an 𝑛𝑛 state NFA into a 2𝑛𝑛-state DFA

Could there be a construction that always produces, say, an 𝑛𝑛2-state DFA?

Theorem: For every 𝑛𝑛 ≥ 1, there is a language 𝐿𝐿𝑛𝑛 such that

1. There is an 𝑛𝑛 + 1 -state NFA recognizing 𝐿𝐿𝑛𝑛.

2. There is no DFA recognizing 𝐿𝐿𝑛𝑛 with fewer than 2𝑛𝑛 states.

Conclusion: For finite automata, nondeterminism provides an exponential savings over determinism (in the worst case).

1/29/2020 CS332 – Theory of Computation 23

More on Closure Properties

1/29/2020 CS332 – Theory of Computation 24

∗

Let 𝐴𝐴, 𝐵𝐵 ⊆{Σ be languages. Define

Operations on languages

Regular Operations

Union: 𝐴𝐴 ∪ 𝐵𝐵

Concatenation:𝐴𝐴 ∘𝐵𝐵= 𝑎𝑎𝑎𝑎 𝑎𝑎∈𝐴𝐴,𝑎𝑎∈𝐵𝐵} Star:𝐴𝐴∗ ={𝑎𝑎1𝑎𝑎2…𝑎𝑎𝑛𝑛|𝑛𝑛 ≥0and𝑎𝑎𝑖𝑖 ∈𝐴𝐴}

Complement: 𝐴𝐴̅

Intersection: 𝐴𝐴 ∩ 𝐵𝐵

Reverse: 𝐴𝐴𝑅𝑅 = { 𝑎𝑎1𝑎𝑎2…𝑎𝑎𝑛𝑛|𝑎𝑎𝑛𝑛…𝑎𝑎1 ∈ 𝐴𝐴}

Theorem: The class of regular languages is closed under all six of these operations

1/29/2020 CS332 – Theory of Computation 25

Closure under Reverse

Theorem. The reverse of a regular language is also regular

Proof: Let 𝐿𝐿 be a regular language and 𝑀𝑀 be a DFA recognizing it.

Construct an NFA 𝑀𝑀′ recognizing 𝐿𝐿𝑅𝑅:

• Define 𝑀𝑀𝑀 as 𝑀𝑀 with the arrows reversed.

• Make the start state of 𝑀𝑀 be the accept state in 𝑀𝑀𝑀.

ε

ε

ε

• Make a new start state that goes to all accept states of 𝑀𝑀 by ε-transitions.

1/29/2020 CS332 – Theory of Computation

26

Closure under Concatenation

Concatenation:𝐴𝐴∘𝐵𝐵 = {𝑎𝑎𝑎𝑎|𝑎𝑎∈𝐴𝐴and𝑎𝑎∈𝐵𝐵}

Theorem. If 𝐴𝐴 and 𝐵𝐵 are regular, 𝐴𝐴 ∘ 𝐵𝐵 is also regular.

Proof: Given DFAs 𝑀𝑀𝐴𝐴 and 𝑀𝑀𝐵𝐵, construct NFA by

• Connecting all accept states in 𝑀𝑀𝐴𝐴 to the start state in 𝑀𝑀𝐵𝐵. • Make all states in 𝑀𝑀𝐴𝐴 non-accepting.

ε 𝐿𝐿(𝑀𝑀𝐵𝐵) = 𝐵𝐵

1/29/2020 CS332 – Theory of Computation 27

𝐿𝐿(𝑀𝑀𝐴𝐴) = 𝐴𝐴

A Mystery Construction

Given DFAs 𝑀𝑀𝐴𝐴 recognizing 𝐴𝐴 and 𝑀𝑀𝐵𝐵 recognizing 𝐵𝐵, what does the following NFA recognize?

ε ε

𝐿𝐿(𝑀𝑀𝐴𝐴) = 𝐴𝐴

𝐿𝐿(𝑀𝑀𝐵𝐵) = 𝐵𝐵

1/29/2020

CS332 – Theory of Computation 28

Closure under Star

Star:𝐴𝐴∗ ={𝑎𝑎1𝑎𝑎2…𝑎𝑎𝑛𝑛|𝑛𝑛 ≥0and𝑎𝑎𝑖𝑖 ∈𝐴𝐴} Theorem. If 𝐴𝐴 is regular, 𝐴𝐴∗ is also regular.

𝐿𝐿(𝑀𝑀) = 𝐴𝐴

1/29/2020 CS332 – Theory of Computation 29