## CS310 : Automata Theory 2020

### Lecture 16: Minimization and other decision problems

Instructor: S. Akshay

IIT Bombay, India

17-02-2020

### Recap

I Automata and algebraic models: DFA, NFA,-NFA, regular expressions.

I Regular languages: All these models accept the same class of languages.

I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions

I Applications: text search using automata, regular expressions in GREP, emacs, python etc.

I Properties and limitations of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemma.

I Examples of non-regular languages and how to show non-regularity using pumping lemma.

I Myhill-Nerode relations, theorem and its applications

I Algorithms forDecision problems for automata/regular languages

### Recap

I Automata and algebraic models: DFA, NFA,-NFA, regular expressions.

I Regular languages: All these models accept the same class of languages.

I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions

I Applications: text search using automata, regular expressions in GREP, emacs, python etc.

I Properties and limitations of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemma.

I Examples of non-regular languages and how to show non-regularity using pumping lemma.

I Myhill-Nerode relations, theorem and its applications

I Algorithms forDecision problems for automata/regular languages

### Recap

I Automata and algebraic models: DFA, NFA,-NFA, regular expressions.

I Regular languages: All these models accept the same class of languages.

I Conversions: from NFA to DFA (Subset construction),-NFA to DFA, Regular expressions to -NFA, DFA to regular expressions

I Applications: text search using automata, regular expressions in GREP, emacs, python etc.

I Properties and limitations of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemma.

I Examples of non-regular languages and how to show non-regularity using pumping lemma.

I

### Checking equivalence of states

Equivalent states

In a DFA (Q,Σ, δ,q0,F), statesp,q are called equivalent if for each wordw, δ(p,ˆ w) is accepting iff ˆδ(q,w) is accepting.

Distinguishable

GivenA= (Q,Σ, δ,q0,F), two states p,q ∈Q are called distinguishableif they are not equivalent, i.e., there exists a wordw such that ˆδ(p,w)∈Lbut ˆδ(q,w)6∈L.

Asaturation algorithm for identifying all distinguishable states: I base case: p,q are distinguishable ifp ∈F but q6∈F.

I recursive step; p,q are distinguishable if on reading someletter they take us to an already distinguishable pair of states!

Algorithm for checking equivalence ofp,q I Run the above algorithm until saturation.

I If at end, p,q are still not marked distinguishable, then they are equivalent!

### Checking equivalence of states

Equivalent states

In a DFA (Q,Σ, δ,q0,F), statesp,q are called equivalent if for each wordw, δ(p,ˆ w) is accepting iff ˆδ(q,w) is accepting.

Distinguishable

Given A= (Q,Σ, δ,q0,F), two statesp,q ∈Q are called distinguishableif they are not equivalent, i.e., there exists a word w such that ˆδ(p,w)∈Lbut δ(q,ˆ w)6∈L.

Asaturation algorithm for identifying all distinguishable states: I base case: p,q are distinguishable ifp ∈F but q6∈F.

I recursive step; p,q are distinguishable if on reading someletter they take us to an already distinguishable pair of states!

Algorithm for checking equivalence ofp,q I Run the above algorithm until saturation.

I If at end, p,q are still not marked distinguishable, then they are equivalent!

### Checking equivalence of states

Equivalent states

In a DFA (Q,Σ, δ,q0,F), statesp,q are called equivalent if for each wordw, δ(p,ˆ w) is accepting iff ˆδ(q,w) is accepting.

Distinguishable

Given A= (Q,Σ, δ,q0,F), two statesp,q ∈Q are called distinguishableif they are not equivalent, i.e., there exists a word w such that ˆδ(p,w)∈Lbut δ(q,ˆ w)6∈L.

A saturation algorithm for identifying all distinguishable states:

I base case: p,q are distinguishable ifp ∈F but q6∈F.

I recursive step; p,q are distinguishable if on reading someletter they take us to an already distinguishable pair of states!

Algorithm for checking equivalence ofp,q I Run the above algorithm until saturation.

I If at end, p,q are still not marked distinguishable, then they are equivalent!

### Checking equivalence of states

Equivalent states

Distinguishable

Given A= (Q,Σ, δ,q0,F), two statesp,q ∈Q are called distinguishableif they are not equivalent, i.e., there exists a word w such that ˆδ(p,w)∈Lbut δ(q,ˆ w)6∈L.

A saturation algorithm for identifying all distinguishable states:

I base case: p,q are distinguishable ifp ∈F but q6∈F.

Algorithm for checking equivalence of p,q

### Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

1 0

0 1

0 1

0 1 1

0 0

1

q1

*

q2

* *

q_{3}

* * *

q4

* * *

q5

* * * *

q_{6}

* * * * * *

* * * * * *

Distinguishing words I

I 0 I 1 I 01

### Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

1 0

0 1

0 1

0 1 1

0 0

1

q1

*

q2 * *
q_{3}

* *

* q4

*

*

*

* * *

* * * * *

* * * * *

Distinguishing words I

I 0 I 1 I 01

### Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

1 0

0 1

0 1

0 1 1

0 0

1

q1

*

q2 * *
q_{3} * * *
q4

*

* *

q5 * * * *

q_{6}

* *

* *

*

*

* * *

Distinguishing words I

I 0

I 1 I 01

### Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

1 0

0 1

0 1

0 1 1

0 0

1

q1 *
q2 * *
q_{3} * * *

q4 * * *

* *

Distinguishing words I

I 01

### Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

1 0

0 1

0 1

0 1 1

0 0

1

q1 *
q2 * *
q_{3} * * *

q4 * * *

q5 * * * *

q_{6} * * * * * *

Distinguishing words I

I 0 I 1

### Checking equivalence of states

Theorem

If two states are not distinguished by the table-filling algorithm, then they are equivalent.

Exercise: Prove this! Hint:

I Suppose not. There must be a pair of states that are distinguishable but not found by algorithm.

I Over all suchbadpairs, consider theshortest string that distinguishes a bad pair (p,q).

I Let w =a_{1}. . .a_{n}. The pair of states reached after a_{1} can be
distinguished! (Canw =?)

I Can this pair of states be a bad pair? Reason about this and finish proof!

### Checking equivalence of states

Theorem

If two states are not distinguished by the table-filling algorithm, then they are equivalent.

Exercise: Prove this!

Hint:

I Suppose not. There must be a pair of states that are distinguishable but not found by algorithm.

I Over all suchbadpairs, consider theshortest string that distinguishes a bad pair (p,q).

I Let w =a_{1}. . .a_{n}. The pair of states reached after a_{1} can be
distinguished! (Canw =?)

I Can this pair of states be a bad pair? Reason about this and finish proof!

### Checking equivalence of states

Theorem

If two states are not distinguished by the table-filling algorithm, then they are equivalent.

Exercise: Prove this! Hint:

I Suppose not. There must be a pair of states that are distinguishable but not found by algorithm.

I Over all suchbadpairs, consider theshortest string that distinguishes a bad pair (p,q).

I Let w =a_{1}. . .a_{n}. The pair of states reached after a_{1} can be
distinguished! (Canw =?)

I Can this pair of states be a bad pair? Reason about this and finish proof!

### Checking equivalence of states

Theorem

If two states are not distinguished by the table-filling algorithm, then they are equivalent.

Exercise: Prove this! Hint:

I Suppose not. There must be a pair of states that are distinguishable but not found by algorithm.

I Over all suchbadpairs, consider theshortest string that distinguishes a bad pair (p,q).

_{1}. . .a_{n}. The pair of states reached after a_{1} can be
distinguished! (Canw =?)

I Can this pair of states be a bad pair? Reason about this and finish proof!

### Checking equivalence of states

Theorem

If two states are not distinguished by the table-filling algorithm, then they are equivalent.

Exercise: Prove this! Hint:

I Suppose not. There must be a pair of states that are distinguishable but not found by algorithm.

I Over all suchbadpairs, consider theshortest string that distinguishes a bad pair (p,q).

_{1}. . .a_{n}. The pair of states reached after a_{1} can be
distinguished! (Canw =?)

I Can this pair of states be a bad pair? Reason about this and finish proof!

### Checking equivalence of states

Theorem

If two states are not distinguished by the table-filling algorithm, then they are equivalent.

Exercise: Prove this! Hint:

I Suppose not. There must be a pair of states that are distinguishable but not found by algorithm.

I Over all suchbadpairs, consider theshortest string that distinguishes a bad pair (p,q).

_{1}. . .a_{n}. The pair of states reached after a_{1} can be
distinguished! (Canw =?)

I Can this pair of states be a bad pair? Reason about this and finish proof!

### Other Decision problems

I Is a language empty?

I Is a word belongs to a language?

I Does a language contain another language?

Difficulty of the question depends on the representation of the language.

### Other Decision problems

I Is a language empty?

I Is a word belongs to a language?

I Does a language contain another language?

Difficulty of the question depends on the representation of the language.

### Other Decision problems

I Is a language empty?

I Is a word belongs to a language?

I Does a language contain another language?

Difficulty of the question depends on the representation of the language.

### Other Decision problems

I Is a language empty?

I Is a word belongs to a language?

I Does a language contain another language?

Difficulty of the question depends on the representation of the language.

### Is L empty?

L is given as I DFAor NFA

I Check if reachable states from the initial state include any accepting state
I Cost of finding reachable statesO(n^{2}), wherenis the number of states

I RE

Traverse RE bottom up and apply the following rules. I ∅is empty.

I andaare notempty.

I L_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.
I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.
I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is L empty?

L is given as I DFAor NFA

I Check if reachable states from the initial state include any accepting state
I Cost of finding reachable statesO(n^{2}), wherenis the number of states
I RE

Traverse RE bottom up and apply the following rules. I ∅is empty.

I andaare notempty.

I L_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.
I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.
I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is L empty?

L is given as I DFAor NFA

I Check if reachable states from the initial state include any accepting state
I Cost of finding reachable statesO(n^{2}), wherenis the number of states
I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.
I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.
I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is L empty?

L is given as I DFAor NFA

I Check if reachable states from the initial state include any accepting state
I Cost of finding reachable statesO(n^{2}), wherenis the number of states
I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.
I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.
I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is L empty?

L is given as I DFAor NFA

^{2}), wherenis the number of states
I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.

I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.
I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is L empty?

L is given as I DFAor NFA

^{2}), wherenis the number of states
I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.

I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.

I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is L empty?

L is given as I DFAor NFA

^{2}), wherenis the number of states
I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.

I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.

I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is L empty?

L is given as I DFAor NFA

^{2}), wherenis the number of states
I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L_{1}+L_{2}is empty ifbothL_{1} andL_{2} are empty.

I L_{1}L_{2} is empty ifeitherL_{1} orL_{2}are empty.

I L^{∗}_{1} is notempty.(why?)

Cost of deciding the emptiness O(n), n is the size of RE.

### Is w ∈ L?

Language is given as I DFA

I run it onw and check if an accepting state is reached I Cost or running DFAO(|w|)

I NFA

I compute reachable states onw

I Cost or running NFAO(|w|n^{2}), where nis the number of states

Exercise 1

What is the cost of checking membership ifL is given asRE? Exercise 2

For regular languagesL1 and L2, how do we checkL1 =L2?

### Is w ∈ L?

Language is given as I DFA

I run it onw and check if an accepting state is reached I Cost or running DFAO(|w|)

I NFA

I compute reachable states onw

I Cost or running NFAO(|w|n^{2}), where nis the number of states

Exercise 1

What is the cost of checking membership ifL is given asRE? Exercise 2

For regular languagesL1 and L2, how do we checkL1 =L2?

### Is w ∈ L?

Language is given as I DFA

I run it onw and check if an accepting state is reached I Cost or running DFAO(|w|)

I NFA

I compute reachable states onw

I Cost or running NFAO(|w|n^{2}), where nis the number of states

Exercise 1

What is the cost of checking membership ifL is given asRE? Exercise 2

For regular languagesL1 and L2, how do we checkL1 =L2?

### Is w ∈ L?

Language is given as I DFA

I run it onw and check if an accepting state is reached I Cost or running DFAO(|w|)

I NFA

I compute reachable states onw

I Cost or running NFAO(|w|n^{2}), where nis the number of states

Exercise 1

What is the cost of checking membership if L is given asRE?

Exercise 2

For regular languagesL1 and L2, how do we checkL1 =L2?

### Is w ∈ L?

Language is given as I DFA

I run it onw and check if an accepting state is reached I Cost or running DFAO(|w|)

I NFA

I compute reachable states onw

I Cost or running NFAO(|w|n^{2}), where nis the number of states

Exercise 1

What is the cost of checking membership if L is given asRE?

### Regular language equivalence checking

Decision problem

Given two regular languages L1 andL2, decide if L1=L2.

1. Convert them into DFAA1 andA2 respectively.

2. Run the table-filling algorithm on the automata as if they were one. Theorem

The initial states ofA1 andA2 are equivalent iffL1 =L2.

### Regular language equivalence checking

Decision problem

Given two regular languages L1 andL2, decide if L1=L2. 1. Convert them into DFAA1 andA2 respectively.

2. Run the table-filling algorithm on the automata as if they were one. Theorem

The initial states ofA1 andA2 are equivalent iffL1 =L2.

### Regular language equivalence checking

Decision problem

Given two regular languages L1 andL2, decide if L1=L2. 1. Convert them into DFAA1 andA2 respectively.

2. Run the table-filling algorithm on the automata as if they were one.

Theorem

The initial states of A1 andA2 are equivalent iffL1=L2.

### Example : language equivalence checking

Example 16.1

Run the Table-filling algorithm on the following automata as if they are one.

q0

start q1 start q2 q3

q4

0

1 0

1

0 1

0

1 1

0

We obtain the followingD set
q_{1} *

q2 *

q3 *

q_{4} * * *

D q_{0} q_{1} q_{2} q_{3}

Sinceq_{0}andq_{2}are not distinguishable,
the automata have same language.

### Example : language equivalence checking

Example 16.1

Run the Table-filling algorithm on the following automata as if they are one.

q0

start q1 start q2 q3

q4

0

1 0

1

0 1

0

1 1

0 We obtain the following D set

q_{1} *

q2 *

q3 *

q * * *

Sinceq_{0}andq_{2}are not distinguishable,
the automata have same language.

### Example : language equivalence checking

Example 16.1

Run the Table-filling algorithm on the following automata as if they are one.

q0

start q1 start q2 q3

q4

0

1 0

1

0 1

0

1 1

0 We obtain the following D set

q_{1} *

### Minimization

Given a DFA, how do we get the one with minimum number of states which accepts the same language?

Algorithm for minimization

I Identify equivalent states using the table-filling algo.

I collapse them and remove redundant states I At end we will obtain a minimal automaton.

I In fact, we “obtain” the Myhill-Nerode construction upto renaming of states

### Minimization

Given a DFA, how do we get the one with minimum number of states which accepts the same language?

Algorithm for minimization

I Identify equivalent states using the table-filling algo.

I collapse them and remove redundant states

I At end we will obtain a minimal automaton.

I In fact, we “obtain” the Myhill-Nerode construction upto renaming of states

### Minimization

Given a DFA, how do we get the one with minimum number of states which accepts the same language?

Algorithm for minimization

I Identify equivalent states using the table-filling algo.

I collapse them and remove redundant states I At end we will obtain a minimal automaton.

I In fact, we “obtain” the Myhill-Nerode construction upto renaming of states

### Example : DFA minimization

Example 16.2

After applying the minimization, we obtain.

B_{0}

start B_{1} B_{2}

B_{5} B_{6}
0

1

1 0

1 0

0 1 1

0

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFAA^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial statesq_{0} andq_{0}^{0} of Aand A^{0} respectively are equivalent.
claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofA are reachable from its initial state(why?). Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q andq^{0} must be equivalent. Otherwise,q0 andq^{0}_{0} are not equivalent.^{(why?)}

q_{0}

start start q_{0}^{0}

A A^{0}

q w

q^{0}
w

...

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial statesq_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.
claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofA are reachable from its initial state(why?). Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q andq^{0} must be equivalent. Otherwise,q0 andq^{0}_{0} are not equivalent.^{(why?)}

q_{0}

start start q_{0}^{0}

A A^{0}

q w

q^{0}
w

...

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial states q_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.

claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofA are reachable from its initial state(why?). Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q and q^{0} must be equivalent. Otherwise, q0 andq^{0}_{0} are not equivalent.^{(why?)}

q_{0}

start start q_{0}^{0}

A A^{0}

q w

q^{0}
w

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial states q_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.

claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofA are reachable from its initial state(why?). Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q and q^{0} must be equivalent. Otherwise, q0 andq^{0}_{0} are not equivalent.^{(why?)}

start q start q^{0}

q w

q^{0}
w

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial states q_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.

claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofAare reachable from its initial state^{(why?)}.

Letq be a state inA. Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q and q^{0} must be equivalent. Otherwise, q0 andq^{0}_{0} are not equivalent.^{(why?)}

q_{0}

start start q_{0}^{0}

A A^{0}

q w

q^{0}
w

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial states q_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.

claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofAare reachable from its initial state^{(why?)}.
Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q and q^{0} must be equivalent. Otherwise, q0 andq^{0}_{0} are not equivalent.^{(why?)}

start q q start q^{0}

w

q^{0}
w

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial states q_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.

claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofAare reachable from its initial state^{(why?)}.
Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q and q^{0} must be equivalent. Otherwise, q0 andq^{0}_{0} are not equivalent.^{(why?)}

q_{0}

start start q_{0}^{0}

A A^{0}

q w

q^{0}
w

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial states q_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.

claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofAare reachable from its initial state^{(why?)}.
Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q and q^{0} must be equivalent. Otherwise, q0 andq^{0}_{0} are not equivalent.^{(why?)}

start q w q start q^{0}

q^{0}
w

### Unique minimum DFA

Theorem 16.1

Let A be a minimized DFA. No DFA smaller than A recognizes L(A).

Proof.

Assume a DFA A^{0} such that A^{0} has fewer states than AandL(A) =L(A^{0}).

Therefore, initial states q_{0} andq^{0}_{0} of Aand A^{0} respectively are equivalent.

claim: All states of Aare equivalent to some state ofA^{0}.

We know all states ofAare reachable from its initial state^{(why?)}.
Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA^{0} to some state q^{0}.

q and q^{0} must be equivalent. Otherwise, q0 andq^{0}_{0} are not equivalent.^{(why?)}
q_{0}

start start q_{0}^{0}

A A^{0}

q w

q^{0}
w

### Unique minimization DFA

Proof(Contd.)

Due to the pigeonhole principle, there are statesq_{1} andq_{2} of Asuch that
they are equivalent to the same state of A^{0}.

Therefore,q1 andq2 are equivalent.

SinceAis minimized, no two states ofA are equivalent. Contradiction. In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

### Unique minimization DFA

Proof(Contd.)

Due to the pigeonhole principle, there are statesq_{1} andq_{2} of Asuch that
they are equivalent to the same state of A^{0}.

Therefore, q1 andq2 are equivalent.

SinceAis minimized, no two states ofA are equivalent. Contradiction. In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

### Unique minimization DFA

Proof(Contd.)

Due to the pigeonhole principle, there are statesq_{1} andq_{2} of Asuch that
they are equivalent to the same state of A^{0}.

Therefore, q1 andq2 are equivalent.

Since Ais minimized, no two states ofA are equivalent. Contradiction.

In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

### Unique minimization DFA

Proof(Contd.)

_{1} andq_{2} of Asuch that
they are equivalent to the same state of A^{0}.

Therefore, q1 andq2 are equivalent.

Since Ais minimized, no two states ofA are equivalent. Contradiction.

In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

### Moving on

If we wish to add expressive power to DFA, what must be do?

Suggestions?

### Moving on

If we wish to add expressive power to DFA, what must be do?

Suggestions?