Lecture 16: Minimization and other decision problems

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

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

* * *

q4

* * *

q5

* * * *

q₆

* * * * * *

* * * * * *

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₃

* *

* 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₃ * * * q4

*

* *

q5 * * * *

q₆

* *

* *

*

*

* * *

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₃ * * *

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₃ * * *

q4 * * *

q5 * * * *

q₆ * * * * * *

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₁. . .a_n. The pair of states reached after a₁ 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₁. . .a_n. The pair of states reached after a₁ 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₁. . .a_n. The pair of states reached after a₁ 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₁. . .a_n. The pair of states reached after a₁ 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₁. . .a_n. The pair of states reached after a₁ 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₁. . .a_n. The pair of states reached after a₁ 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²), wherenis the number of states

I RE

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

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty. I L₁L₂ is empty ifeitherL₁ orL₂are empty. I L^∗₁ 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²), wherenis the number of states I RE

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

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty. I L₁L₂ is empty ifeitherL₁ orL₂are empty. I L^∗₁ 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²), wherenis the number of states I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty. I L₁L₂ is empty ifeitherL₁ orL₂are empty. I L^∗₁ 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²), wherenis the number of states I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty. I L₁L₂ is empty ifeitherL₁ orL₂are empty. I L^∗₁ 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²), wherenis the number of states I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty.

I L₁L₂ is empty ifeitherL₁ orL₂are empty. I L^∗₁ 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²), wherenis the number of states I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty.

I L₁L₂ is empty ifeitherL₁ orL₂are empty.

I L^∗₁ 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²), wherenis the number of states I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty.

I L₁L₂ is empty ifeitherL₁ orL₂are empty.

I L^∗₁ 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²), wherenis the number of states I RE

Traverse RE bottom up and apply the following rules.

I ∅is empty.

I andaare notempty.

I L₁+L₂is empty ifbothL₁ andL₂ are empty.

I L₁L₂ is empty ifeitherL₁ orL₂are empty.

I L^∗₁ 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²), 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²), 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²), 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²), 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²), 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₁ *

q2 *

q3 *

q₄ * * *

D q₀ q₁ q₂ q₃

Sinceq₀andq₂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₁ *

q2 *

q3 *

q * * *

Sinceq₀andq₂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₁ *

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₀

start B₁ B₂

B₅ B₆ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial statesq₀ andq₀⁰ of Aand A⁰ respectively are equivalent. claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q andq⁰ must be equivalent. Otherwise,q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial statesq₀ andq⁰₀ of Aand A⁰ respectively are equivalent. claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q andq⁰ must be equivalent. Otherwise,q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?)

start q start q⁰

q w

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

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

Letq be a state inA. Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?)

start q q start q⁰

w

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?)

start q w q start q⁰

q⁰ 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⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

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

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?) q₀

start start q₀⁰

A A⁰

q w

q⁰ w

Unique minimization DFA

Proof(Contd.)

Due to the pigeonhole principle, there are statesq₁ andq₂ of Asuch that they are equivalent to the same state of A⁰.

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₁ andq₂ of Asuch that they are equivalent to the same state of A⁰.

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₁ andq₂ of Asuch that they are equivalent to the same state of A⁰.

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

Due to the pigeonhole principle, there are statesq₁ andq₂ of Asuch that they are equivalent to the same state of A⁰.

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?