CS310 : Automata Theory 2020

(1)

CS310 : Automata Theory 2020 Instructor: S. Akshay IIT Bombay, India 1

CS310 : Automata Theory 2020

Lecture 5: NFA to DFA: blowup and more

Instructor: S. Akshay

IIT Bombay, India

21-01-2020

(2)

Logistics

Course material online

https://www.cse.iitb.ac.in/~akshayss/courses/cs310-2020/

Discussions

I For online discussions: Piazza

I Problem solving session: Next Tuesday at 7pm.

I Quiz 1 Timing: Friday 31st Jan at 7.15pm

I Office hours for doubt clearance: Today at 7.30pm at CC 504.

(3)

Logistics

Course material online

https://www.cse.iitb.ac.in/~akshayss/courses/cs310-2020/

Discussions

I For online discussions: Piazza

I Problem solving session: Next Tuesday at 7pm.

I Quiz 1 Timing: Friday 31st Jan at 7.15pm

I Office hours for doubt clearance: Today at 7.30pm at CC 504.

(4)

Recap

I Deterministic finite state automata

I Formal definition, run, accepting run, (extended) transition relation I Closure under Union, intersection and complementation

I Non-deterministic finite state automata I From NFA to DFA: The Subset construction

(5)

Power of NFA

Theorem

For each NFA A, there exists a DFAA⁰ such thatL(A) =L(A⁰).

Proof:

1. Let A= (Q,Σ, δ,q0,F) be the given NFA.

2. Construction: we define a DFA A⁰= (P(Q),Σ,δ⁰,{q₀},F⁰) where I for eachS ⊆Q,δ⁰(S,a) :=∪_q∈Sδ(q,a)

I F⁰ :={S ⊆Q|S∩F6=∅}, i.e., all subsets ofQ that have some state fromF.

3. Proof of correctness: we need to show that L(A⁰) =L(A).

(6)

Power of NFA

Theorem

Proof:

(7)

Power of NFA

Theorem

Proof:

(8)

Power of NFA

Theorem

Proof:

3. Proof of correctness: we need to show thatL(A⁰) =L(A).

(9)

Proof of subset construction continued

Lemma: for all w ∈Σ^∗, ˆδ(q0,w) = ˆδ⁰({q0},w)

Proof:

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q₀}= ˆδ⁰({q₀}, ). 3. Induction step: let w =xa for x ∈Σ^∗,a∈Σ.

3.1 By induction hypothesis, ˆδ(q0,x) = ˆδ⁰({q0},x) =S, say. 3.2 By definition of ˆδ, ˆδ(q0,xa) =∪_q∈Sδ(q,a).

3.3 By definition of ˆδ⁰, ˆδ⁰({q0},xa) =δ⁰(S,a) =∪_q∈Sδ(q,a). 3.4 Therefore, ˆδ(q0,xa) = ˆδ⁰({q0},xa).

3.5 By induction, the proof is complete.

(10)

Proof of subset construction continued

Lemma: for all w ∈Σ^∗, ˆδ(q0,w) = ˆδ⁰({q0},w) Proof:

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q₀}= ˆδ⁰({q₀}, ). 3. Induction step: let w =xa for x ∈Σ^∗,a∈Σ.

(11)

Proof of subset construction continued

2. Base case: |w|= 0,

w =, ˆδ(q0, ) ={q₀}= ˆδ⁰({q₀}, ). 3. Induction step: let w =xa for x ∈Σ^∗,a∈Σ.

(12)

Proof of subset construction continued

2. Base case: |w|= 0, w =,

δ(qˆ 0, ) ={q₀}= ˆδ⁰({q₀}, ). 3. Induction step: let w =xa for x ∈Σ^∗,a∈Σ.

(13)

Proof of subset construction continued

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q₀}= ˆδ⁰({q₀}, ).

3. Induction step: let w =xa for x ∈Σ^∗,a∈Σ.

(14)

Proof of subset construction continued

(15)

Proof of subset construction continued

3.1 By induction hypothesis, ˆδ(q0,x) = ˆδ⁰({q0},x) =S, say.

3.2 By definition of ˆδ, ˆδ(q0,xa) =∪_q∈Sδ(q,a).

(16)

Proof of subset construction continued

(17)

Proof of subset construction continued

3.3 By definition of ˆδ⁰, ˆδ⁰({q0},xa) =δ⁰(S,a) =∪_q∈Sδ(q,a).

3.4 Therefore, ˆδ(q0,xa) = ˆδ⁰({q0},xa). 3.5 By induction, the proof is complete.

(18)

Proof of subset construction continued

3.4 Therefore, ˆδ(q0,xa) = ˆδ⁰({q0},xa).

(19)

Proof of subset construction continued

3.4 Therefore, ˆδ(q0,xa) = ˆδ⁰({q0},xa).

(20)

Proof of correctness of the subset construction

Theorem

Proof:

1. Let A= (Q,Σ, δ,q₀,F) be the given NFA.

2. Construction: we define a DFA A⁰= (P(Q),Σ,δ⁰,{q₀},F⁰) where I for eachS ⊆Q,δ⁰(S,a) :=∪q∈Sδ(q,a)

3. Proof of correctness: To show that L(A⁰) =L(A).

3.1 From Lemma, we have for allw ∈Σ^∗, ˆδ(q₀,w) = ˆδ⁰({q₀},w). 3.2 Hence, for allw, ˆδ(q₀,w)∩F 6=∅iff ˆδ⁰({q₀},w)∈F⁰. 3.3 Thus,w is accepted byAiffw is accepted byA⁰. 3.4 Therefore,L(A⁰) =L(A), which completes the proof.

(21)

Proof of correctness of the subset construction

Theorem

Proof:

3.1 From Lemma, we have for allw ∈Σ^∗, ˆδ(q₀,w) = ˆδ⁰({q₀},w). 3.2 Hence, for allw, ˆδ(q₀,w)∩F 6=∅iff ˆδ⁰({q₀},w)∈F⁰. 3.3 Thus,w is accepted byAiffw is accepted byA⁰. 3.4 Therefore,L(A⁰) =L(A), which completes the proof.

(22)

Proof of correctness of the subset construction

Theorem

Proof:

3.1 From Lemma, we have for allw ∈Σ^∗, ˆδ(q₀,w) = ˆδ⁰({q₀},w).

3.2 Hence, for allw, ˆδ(q₀,w)∩F 6=∅iff ˆδ⁰({q₀},w)∈F⁰. 3.3 Thus,w is accepted byAiffw is accepted byA⁰. 3.4 Therefore,L(A⁰) =L(A), which completes the proof.

(23)

Proof of correctness of the subset construction

Theorem

Proof:

3.2 Hence, for allw, ˆδ(q₀,w)∩F 6=∅iff ˆδ⁰({q₀},w)∈F⁰.

3.3 Thus,w is accepted byAiffw is accepted byA⁰. 3.4 Therefore,L(A⁰) =L(A), which completes the proof.

(24)

Proof of correctness of the subset construction

Theorem

Proof:

3.2 Hence, for allw, ˆδ(q₀,w)∩F 6=∅iff ˆδ⁰({q₀},w)∈F⁰. 3.3 Thus,w is accepted byAiffw is accepted byA⁰. 3.4 Therefore,L(A⁰) =L(A), which completes the proof.

(25)

Complexity of subset construction

I if NFA has n states, then DFA has

2ⁿ states. I But not all these states need to be reachable!

Two questions

1. Does this blowup really occur when only considering reachable states? 2. On examples where it does not occur can we have a subset construction

that is efficient?

(26)

Complexity of subset construction

I if NFA has n states, then DFA has 2ⁿ states.

I But not all these states need to be reachable!

Two questions

that is efficient?

(27)

Complexity of subset construction

Two questions

that is efficient?

(28)

Complexity of subset construction

Two questions

1. Does this blowup really occur when only considering reachable states?

2. On examples where it does not occur can we have a subset construction that is efficient?

(29)

Worst case blowup of subset construction

I Is one NFA enough?

A family of examples such that for eachn there is an example NFA parametrized by n.

I For each example in family show that if a smaller DFA than 2ⁿ exists, there is a contradiction.

An exponential blowup

I For eachn∈N, letLn={w ∈ {0,1}^∗|n^th symbol from the end is a 1} I Exercise: give an NFA for A_n which acceptsL_n. How many states does

it have?

I CanLn be accepted by a DFA with less than 2ⁿ states?

(30)

Worst case blowup of subset construction

I Is one NFA enough? A family of examples such that for each n there is an example NFA parametrized by n.

I For each example in family show that if a smaller DFA than 2ⁿ exists, there is a contradiction.

it have?

(31)

Worst case blowup of subset construction

I For each example in family show that if a smaller DFA than 2ⁿexists, there is a contradiction.

it have?

(32)

Worst case blowup of subset construction

I For eachn∈N, letLn={w ∈ {0,1}^∗|n^th symbol from the end is a 1}

I Exercise: give an NFA for A_n which acceptsL_n. How many states does it have?

(33)

Worst case blowup of subset construction

(34)

Worst case blowup of subset construction

(35)

Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting Lnhas at least 2ⁿ states.

(36)

Exponential blowup of the subset construction

Theorem

Proof.

1. Suppose not.

(37)

Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting L_nhas at least 2ⁿ states.

Proof.

1. Suppose not. For some n∈N letLn be accepted by DFAAwith less than 2ⁿstates.

(38)

Exponential blowup of the subset construction

Theorem

Proof.

1. Suppose not. For some n∈N letL_n be accepted by DFAAwith less than 2ⁿstates.

2. Then, there exist a₁. . .a_n andb₁. . .b_n that must both end in the same state q. why?

(39)

Exponential blowup of the subset construction

Theorem

Proof.

1. Suppose not. For some n∈N letLn be accepted by DFAAwith less than 2ⁿstates.

2. Then, there exist a1. . .an andb1. . .bn that must both end in the same state q.

I Pigeon-hole principle. Number of words of lengthnis 2ⁿ, hence two words must fall in the same box.

(40)

Exponential blowup of the subset construction

Theorem

Proof.

2. Then, there exist a1. . .an andb1. . .bn that must both end in the same state q.

3. Supposeai andbi are different and wlog letai = 1,bi = 0.

(41)

Exponential blowup of the subset construction

Theorem

Proof.

2. Then, there exist a₁. . .a_n andb₁. . .b_n that must both end in the same state q.

3. Supposeai andbi are different and wlog letai = 1,bi = 0.

4. Consider words

I w =a1. . .ai. . .an0ⁱ⁻¹ I w⁰=b1. . .bi. . .bn0ⁱ⁻¹

(42)

Exponential blowup of the subset construction

Theorem

Proof.

3. Supposea_i andb_i are different and wlog leta_i = 1,b_i = 0.

4. Consider words

I w =a1. . .ai. . .an0ⁱ⁻¹∈Ln

I w⁰=b1. . .bi. . .bn0ⁱ⁻¹6∈Ln

(43)

Exponential blowup of the subset construction

Theorem

Proof.

3. Supposea_i andb_i are different and wlog leta_i = 1,b_i = 0.

4. Consider words

I w =a1. . .ai. . .an0ⁱ⁻¹∈Ln

I w⁰=b1. . .bi. . .bn0ⁱ⁻¹6∈Ln

5. But Ais a DFA, so starting from q on reading 0ⁱ⁻¹ we reach the same state! HenceA will either accept bothw andw⁰ or reject both.

Contradiction!