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

CS310 : Automata Theory 2020 Instructor: S. Akshay IIT Bombay, India 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.

CS310 : Automata Theory 2020 Instructor: S. Akshay IIT Bombay, India 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.

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

### 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

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

### Power of NFA

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

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

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

I F^{0} :={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^{0}) =L(A).

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

### Power of NFA

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

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

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

I F^{0} :={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^{0}) =L(A).

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

### Power of NFA

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

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

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

I F^{0} :={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^{0}) =L(A).

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

### Power of NFA

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

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

^{0}= (P(Q),Σ,δ^{0},{q_{0}},F^{0}) where
I for eachS ⊆Q,δ^{0}(S,a) :=∪_{q∈S}δ(q,a)

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

3. Proof of correctness: we need to show thatL(A^{0}) =L(A).

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

### Proof of subset construction continued

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

Proof:

1. By induction of|w|.

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

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

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

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

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

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

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

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0,

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

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

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

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

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

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

^{0}({q0},x) =S, say.
3.2 By definition of ˆδ, ˆδ(q0,xa) =∪_{q∈S}δ(q,a).

^{0}, ˆδ^{0}({q0},xa) =δ^{0}(S,a) =∪_{q∈S}δ(q,a).
3.4 Therefore, ˆδ(q0,xa) = ˆδ^{0}({q0},xa).

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q_{0}}= ˆδ^{0}({q_{0}}, ).

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

^{0}({q0},x) =S, say.
3.2 By definition of ˆδ, ˆδ(q0,xa) =∪_{q∈S}δ(q,a).

^{0}, ˆδ^{0}({q0},xa) =δ^{0}(S,a) =∪_{q∈S}δ(q,a).
3.4 Therefore, ˆδ(q0,xa) = ˆδ^{0}({q0},xa).

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q_{0}}= ˆδ^{0}({q_{0}}, ).

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

^{0}({q0},x) =S, say.
3.2 By definition of ˆδ, ˆδ(q0,xa) =∪_{q∈S}δ(q,a).

^{0}, ˆδ^{0}({q0},xa) =δ^{0}(S,a) =∪_{q∈S}δ(q,a).
3.4 Therefore, ˆδ(q0,xa) = ˆδ^{0}({q0},xa).

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q_{0}}= ˆδ^{0}({q_{0}}, ).

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

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

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

^{0}, ˆδ^{0}({q0},xa) =δ^{0}(S,a) =∪_{q∈S}δ(q,a).
3.4 Therefore, ˆδ(q0,xa) = ˆδ^{0}({q0},xa).

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q_{0}}= ˆδ^{0}({q_{0}}, ).

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

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

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

^{0}, ˆδ^{0}({q0},xa) =δ^{0}(S,a) =∪_{q∈S}δ(q,a).
3.4 Therefore, ˆδ(q0,xa) = ˆδ^{0}({q0},xa).

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q_{0}}= ˆδ^{0}({q_{0}}, ).

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

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

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

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

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

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q_{0}}= ˆδ^{0}({q_{0}}, ).

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

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

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

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

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

3.5 By induction, the proof is complete.

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

### Proof of subset construction continued

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

1. By induction of|w|.

2. Base case: |w|= 0, w =, ˆδ(q0, ) ={q_{0}}= ˆδ^{0}({q_{0}}, ).

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

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

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

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

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

3.5 By induction, the proof is complete.

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

### Proof of correctness of the subset construction

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

1. Let A= (Q,Σ, δ,q_{0},F) be the given NFA.

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

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

3. Proof of correctness: To show that L(A^{0}) =L(A).

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

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

### Proof of correctness of the subset construction

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

1. Let A= (Q,Σ, δ,q_{0},F) be the given NFA.

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

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

3. Proof of correctness: To show that L(A^{0}) =L(A).

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

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

### Proof of correctness of the subset construction

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

1. Let A= (Q,Σ, δ,q_{0},F) be the given NFA.

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

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

3. Proof of correctness: To show that L(A^{0}) =L(A).

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

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

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

### Proof of correctness of the subset construction

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

1. Let A= (Q,Σ, δ,q_{0},F) be the given NFA.

^{0}= (P(Q),Σ,δ^{0},{q_{0}},F^{0}) where
I for eachS ⊆Q,δ^{0}(S,a) :=∪q∈Sδ(q,a)

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

3. Proof of correctness: To show that L(A^{0}) =L(A).

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

3.2 Hence, for allw, ˆδ(q_{0},w)∩F 6=∅iff ˆδ^{0}({q_{0}},w)∈F^{0}.

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

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

### Proof of correctness of the subset construction

Theorem

For each NFA A, there exists a DFAA^{0} such thatL(A) =L(A^{0}).

Proof:

1. Let A= (Q,Σ, δ,q_{0},F) be the given NFA.

^{0}= (P(Q),Σ,δ^{0},{q_{0}},F^{0}) where
I for eachS ⊆Q,δ^{0}(S,a) :=∪q∈Sδ(q,a)

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

3. Proof of correctness: To show that L(A^{0}) =L(A).

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

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

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

### Complexity of subset construction

I if NFA has n states, then DFA has

2^{n} 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?

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

### Complexity of subset construction

I if NFA has n states, then DFA has 2^{n} 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?

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

### Complexity of subset construction

I if NFA has n states, then DFA has 2^{n} 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?

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

### Complexity of subset construction

I if NFA has n states, then DFA has 2^{n} 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?

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

### 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^{n} 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^{n} states?

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

### 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^{n} 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^{n} states?

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

### 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^{n}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^{n} states?

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

### 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.

^{n}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^{n} states?

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

### Worst case blowup of subset construction

^{n}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^{n} states?

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

### Worst case blowup of subset construction

^{n}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^{n} states?

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting Lnhas at least 2^{n} states.

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting Lnhas at least 2^{n} states.

Proof.

1. Suppose not.

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting L_{n}has at least 2^{n} states.

Proof.

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

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting Lnhas at least 2^{n} states.

Proof.

1. Suppose not. For some n∈N letL_{n} be accepted by DFAAwith less
than 2^{n}states.

2. Then, there exist a_{1}. . .a_{n} andb_{1}. . .b_{n} that must both end in the same
state q. why?

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting L_{n}has at least 2^{n} states.

Proof.

1. Suppose not. For some n∈N letLn be accepted by DFAAwith less
than 2^{n}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^{n}, hence two words
must fall in the same box.

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting Lnhas at least 2^{n} states.

Proof.

1. Suppose not. For some n∈N letL_{n} be accepted by DFAAwith less
than 2^{n}states.

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.

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting Lnhas at least 2^{n} states.

Proof.

1. Suppose not. For some n∈N letL_{n} be accepted by DFAAwith less
than 2^{n}states.

2. Then, there exist a_{1}. . .a_{n} andb_{1}. . .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−1}
I w^{0}=b1. . .bi. . .bn0^{i−1}

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting L_{n}has at least 2^{n} states.

Proof.

1. Suppose not. For some n∈N letL_{n} be accepted by DFAAwith less
than 2^{n}states.

2. Then, there exist a_{1}. . .a_{n} andb_{1}. . .b_{n} that must both end in the same
state q.

3. Supposea_{i} andb_{i} are different and wlog leta_{i} = 1,b_{i} = 0.

4. Consider words

I w =a1. . .ai. . .an0^{i−1}∈Ln

I w^{0}=b1. . .bi. . .bn0^{i−1}6∈Ln

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

### Exponential blowup of the subset construction

Theorem

For all n ∈N, every DFA accepting L_{n}has at least 2^{n} states.

Proof.

1. Suppose not. For some n∈N letL_{n} be accepted by DFAAwith less
than 2^{n}states.

2. Then, there exist a_{1}. . .a_{n} andb_{1}. . .b_{n} that must both end in the same
state q.

3. Supposea_{i} andb_{i} are different and wlog leta_{i} = 1,b_{i} = 0.

4. Consider words

I w =a1. . .ai. . .an0^{i−1}∈Ln

I w^{0}=b1. . .bi. . .bn0^{i−1}6∈Ln

5. But Ais a DFA, so starting from q on reading 0^{i−1} we reach the same
state! HenceA will either accept bothw andw^{0} or reject both.

Contradiction!