DFA Equivalence and Minimization

(1)

CS 208: Automata Theory and Logic

DFA Equivalence and Minimization Ashutosh Trivedi

A

start B

b

∀x(La(x)→ ∃y.(x<y)∧Lb(y))

a

b

a

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

(2)

Ashutosh Trivedi – 2 of 24

DFA Equivalence and Minimization

1. LetA= (Q,Σ, δ,q0,F)be a DFA.

2. Recall the definition ofextended transition functionδˆ. 3. LetL(A,q)be the languages{w : ˆδ(q,w)∈F}

4. Recall the language ofAis defined asL(A) =L(A,q0). 5. Twostatesq1,q2∈Qare equivalentifL(A,q1) =L(A,q2).

6. We say that twoDFAsA1andA2are equivalentiffL(A1) =L(A2).

Theorem (DFA Equivalence)

For every DFA there exists a unique (up to state naming) minimal DFA.

How to minimize DFAs?

Ashutosh Trivedi DFA Equivalence and Minimization

(3)

DFA Equivalence and Minimization

1. LetA= (Q,Σ, δ,q0,F)be a DFA.

2. Recall the definition ofextended transition functionδˆ. 3. LetL(A,q)be the languages{w : ˆδ(q,w)∈F}

4. Recall the language ofAis defined asL(A) =L(A,q0). 5. Twostatesq1,q2∈Qare equivalentifL(A,q1) =L(A,q2).

6. We say that twoDFAsA1andA2are equivalentiffL(A1) =L(A2).

Theorem (DFA Equivalence)

For every DFA there exists a unique (up to state naming) minimal DFA.

How to minimize DFAs?

(4)

How to minimize a DFA?

Two observations:

– Removing unreachable states: removing states unreachable from the start state does not change the language accepted by a DFA.

– Merging equivalent states: merging equivalent states does not change the language accepted by a DFA.

Algorithms:

1. Breadth-first search or depth-first search(to identify reachable states) 2. table-filling algorithm(by E. F. Moore) (other algorithms exist due to

Hopcroft and Brzozowski)

(5)

How to minimize a DFA?

Two observations:

Algorithms:

(6)

How to minimize a DFA?

Two observations:

Algorithms:

(7)

Table-filling algorithm

– Two states are distinguishable if they are not equivalent.

– Formally, two statesq1,q2aredistinguishable, if there exists a string w∈Σ^∗such thatexactly oneofδ(ˆq1,w)andδ(q2,w)is an accepting state.

– Table-filling algorithmis recursive discovery of distinguishable pairs.

– Basis: Pair(p,q)is distinguishable ifp∈Fandq6∈F.why?

– Induction: Pair(p,q)is distinguishable if statesδ(p,a)andδ(q,a)are distinguishable for somea∈Σ.why?

TABLE-FILLINGALGORITHM:

1. DISTINGUISHABLE={(p,q) : p∈Fandq6∈F}. 2. Repeat while no new pair is added

2.1 for everya∈Σ

add(p,q)to DISTINGUISHABLEif(δ(p,a), δ(q,a))∈DISTINGUISHABLE. 3. Return DISTINGUISHABLE.

(8)

Table-filling algorithm

– Basis: Pair(p,q)is distinguishable ifp∈Fandq6∈F.

why?

2.1 for everya∈Σ

(9)

Table-filling algorithm

2.1 for everya∈Σ

(10)

Table-filling algorithm

– Induction: Pair(p,q)is distinguishable if statesδ(p,a)andδ(q,a)are distinguishable for somea∈Σ.

why?

2.1 for everya∈Σ

(11)

Table-filling algorithm

2.1 for everya∈Σ

(12)

Table-filling algorithm

2.1 for everya∈Σ

(13)

Correctness of Table-Filling Algorithm

Theorem

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

– The proof is by contradiction.

– Assume that there is a pair(p,q)that is not distinguished by the algorithm, but they are not equivalent, i.e. they are indeed distinguishable (it is just that algorithm did not find them). – Let us call such pair(p,q)a bad pair.

– There must be a stringw∈Σ^∗that distinguishes a bad pair(p,q). Let us take shortest such distinguishing stringwamong any bad pair, and consider corresponding bad pair(p,q).

– Notice thatwcan not be (Why?)

– Letwbe of the formax. Sincepandqare distinguishable, we know that exactly one ofδ(p,ˆ ax)andˆδ(q,ax)is accepting.

– Thenp⁰=δ(p,a)andq⁰=δ(q,a)are also distinguished by stringx. – if(p⁰,q⁰)were discovered by table-filling algorithm and(p,q)must have

been discovered as well.

– If(p⁰,q⁰)were not discovered by table-filling algorithm, then(p⁰,q⁰)is a bad pair with a shorter distinguishing string.

(14)

Correctness of Table-Filling Algorithm

Theorem

– Assume that there is a pair(p,q)that is not distinguished by the algorithm, but they are not equivalent, i.e. they are indeed distinguishable (it is just that algorithm did not find them). – Let us call such pair(p,q)a bad pair.

(15)

Correctness of Table-Filling Algorithm

Theorem

– Assume that there is a pair(p,q)that is not distinguished by the algorithm, but they are not equivalent, i.e. they are indeed distinguishable (it is just that algorithm did not find them).

– Let us call such pair(p,q)a bad pair.

(16)

Correctness of Table-Filling Algorithm

Theorem

(17)

Correctness of Table-Filling Algorithm

Theorem

(18)

Correctness of Table-Filling Algorithm

Theorem

– Letwbe of the formax. Sincepandqare distinguishable, we know that exactly one ofδ(p,ˆ ax)andδ(q,ˆ ax)is accepting.

– Thenp⁰=δ(p,a)andq⁰=δ(q,a)are also distinguished by stringx.

– if(p⁰,q⁰)were discovered by table-filling algorithm and(p,q)must have been discovered as well.

(19)

Correctness of Table-Filling Algorithm

Theorem

(20)

Correctness of Table-Filling Algorithm

Theorem

(21)

Minimization of DFAs

– LetAbe a DFA with no unreachable state.

– Let≡_A⊆Q×Qbe thestate equivalence relation(computed by, say table-filling algorithm).

– Note that≡_Ais anequivalence relation.

– Let us write[q]for the equivalence class of the stateq.

– Given a DFAAand≡_Awe can minimizeAto the DFA A≡= (Q⁰,Σ⁰, δ⁰,q⁰₀,F⁰), calledQuotient Automata, where

– Q⁰={[q] : q∈Q}, – Σ⁰= Σ,

– δ⁰([q],a) =δ(q,a)for alla∈Σ, – q⁰₀= [q0], and

– F⁰={[q] : q∈F}.

Theorem

A≡is the minimum and unique (up to state renaming) DFA equivalent to A.

(22)

Minimization of DFAs

– Q⁰={[q] : q∈Q}, – Σ⁰= Σ,

– F⁰={[q] : q∈F}.

Theorem

(23)

Minimization of DFAs

– Q⁰={[q] : q∈Q}, – Σ⁰= Σ,

– F⁰={[q] : q∈F}.

Theorem

(24)

Proof of Minimality

Theorem

Proof.

– Assume that there is a DFABwhose size is smaller thanA≡and accepts that same language.

– Compute equivalent states ofA≡andBusing table-filling algorithm.

– The initial states of both DFAs must be equivalent. (Why?)

– After reading any stringwfrom their initial states, both DFAs will go to states that are equivalent. (Why?)

– For every state ofA≡there is an equivalent state inB.

– Since the number of states ofBare less than that ofA≡, there must be at least two statesp,qofA≡that are equivalent to some state ofB.

– Hencepandqmust be equivalent, a contradiction.

(25)

DFA Equivalence and Minimization

Myhill-Nerode Theorem

Pumping Lemma

(26)

Myhill-Nerode Theorem

– Given a languagesL, two stringsu,v∈Lare equivalent if for all stringsw∈Σwe have thatu.w∈Liffv.w∈L.

– Let≡_L⊆Σ^∗×Σ^∗be such string-equivalence relation.

– Note that≡_Lis an equivalence relation.

– Consider the equivalence classes of≡_L. – When there are only finitely mane classes?

(27)

Myhill-Nerode Theorem

John Myhill Anil Nerode

Theorem (Myhill-Nerode Theorem)

A language L is regular if and only if there exists a string-equivalence relation≡_L with finitely many classes.

Moreover, the number of states in the minimum DFA accepting L is equal to the number of equivalence classes in≡_L.

(28)

Myhill-Nerode Theorem

John Myhill Anil Nerode

Theorem (Myhill-Nerode Theorem)

Moreover, the number of states in the minimum DFA accepting L is equal to the number of equivalence classes in≡_L.

(29)

Myhill-Nerode Theorem

Theorem (Myhill-Nerode Theorem)

Proof.

The proof is in two parts.

– IfLis regular, then a string-equivalence relation≡_Lwith finitely many classes can be given by states of DFA acceptingL.

How? – If there is a string-equivalence relation≡_Lwith finitely many classes,

one can find a DFA acceptingL. How?

(30)

Myhill-Nerode Theorem

Theorem (Myhill-Nerode Theorem)

Proof.

– IfLis regular, then a string-equivalence relation≡_Lwith finitely many classes can be given by states of DFA acceptingL. How?

– If there is a string-equivalence relation≡_Lwith finitely many classes,

(31)

Myhill-Nerode Theorem

Theorem (Myhill-Nerode Theorem)

Proof.

– If there is a string-equivalence relation≡_Lwith finitely many classes, one can find a DFA acceptingL.

How?

(32)

Myhill-Nerode Theorem

Theorem (Myhill-Nerode Theorem)

Proof.

– If there is a string-equivalence relation≡_Lwith finitely many classes,

(33)

Applying Myhill-Nerode Theorem

Theorem (Myhill-Nerode Theorem)

A language L isregularif and only if there exists a string-equivalence relation≡_L with finitely many classes.

Equivalently,

A language L isnonregularif and only if there exists an infinite subset M ofΣ∗ where any two elements of M are distinguishable with respect to L.

(34)

Applying Myhill-Nerode Theorem

Theorem (Myhill-Nerode Theorem)

A language L isregularif and only if there exists a string-equivalence relation≡_L with finitely many classes.

Equivalently,

A language L isnonregularif and only if there exists an infinite subset M ofΣ∗

where any two elements of M are distinguishable with respect to L.

(35)

Applying Myhill-Nerode Theorem

Theorem

The language L={0ⁿ1ⁿ : n≥0}is not regular.

Proof.

1. The proof is bycontradiction. 2. Assume thatLis regular.

3. By Myhill-Nerode theorem, there is a string-equivalence relation≡_L overLwith finitely equivalence classes.

4. Let us consider the set of strings{0,00,000, . . . ,0ⁱ, . . .}.

5. It must be the case that some two string 0^mand 0ⁿ, withm6=nare mapped to same equivalence class.

6. It implies that for all stringsw∈Σ^∗we have that 0^m.w∈Liff 0ⁿ.w∈L. 7. However, 0^m1^m∈Lbut 0ⁿ1^m6∈L, a contradiction.

8. HenceLis not regular.

(36)

Applying Myhill-Nerode Theorem

Theorem

Proof.

1. The proof is bycontradiction.

2. Assume thatLis regular.

(37)

Applying Myhill-Nerode Theorem

Theorem

Proof.

(38)

Applying Myhill-Nerode Theorem

Theorem

Proof.

(39)

Applying Myhill-Nerode Theorem

Theorem

Proof.

(40)

Applying Myhill-Nerode Theorem

Theorem

Proof.

6. It implies that for all stringsw∈Σ^∗we have that 0^m.w∈Liff 0ⁿ.w∈L.

7. However, 0^m1^m∈Lbut 0ⁿ1^m6∈L, a contradiction. 8. HenceLis not regular.

(41)

Applying Myhill-Nerode Theorem

Theorem

Proof.

6. It implies that for all stringsw∈Σ^∗we have that 0^m.w∈Liff 0ⁿ.w∈L.

7. However, 0^m1^m∈Lbut 0ⁿ1^m6∈L, a contradiction.

(42)

Applying Myhill-Nerode Theorem

Theorem

Proof.

1. From Myhill-Nerode theorem, a language L isnonregularif and only if there exists an infinite subsetMofΣ∗where any two elements ofM are distinguishable with respect toL.

2. Consider the setM={0ⁱ : i≥0}.

3. Since any two string inMare distinguishable with respect toL(i.e. 0^m0ⁿ∈Lbut 0ⁿ1^m6∈Lforn6=m), it follows from Myhill-Nerode theorem thatLis a non-regular language.

(43)

Applying Myhill-Nerode Theorem

Theorem

Proof.

(44)

Applying Myhill-Nerode Theorem

Theorem

Proof.

(45)

Applying Myhill-Nerode Theorem

Theorem

Proof.

3. Since any two string inMare distinguishable with respect toL(i.e.

0^m0ⁿ∈Lbut 0ⁿ1^m6∈Lforn6=m), it follows from Myhill-Nerode theorem thatLis a non-regular language.

(46)

Some languages are not regular!

The following languages are regular or non-regular?

– The language{0ⁿ1ⁿ : n≥0}

– The set of strings having an equal number of 0’s and 1’s

– The set of strings with an equal number of occurrences of 01 and 10.

– The language{ww : w∈ {0,1}^∗} – The language{ww : w∈ {0,1}^∗} – The language{0ⁱ1^j : i>j} – The language{0ⁱ1^j : i≤j}

– The language of palindromes of{0,1}

(47)

Some languages are not regular!

The following languages are regular or non-regular?

– The language{0ⁿ1ⁿ : n≥0}

– The set of strings having an equal number of 0’s and 1’s

– The set of strings with an equal number of occurrences of 01 and 10.

– The language{ww : w∈ {0,1}^∗} – The language{ww : w∈ {0,1}^∗} – The language{0ⁱ1^j : i>j} – The language{0ⁱ1^j : i≤j}

– The language of palindromes of{0,1}

(48)

DFA Equivalence and Minimization

Myhill-Nerode Theorem

Pumping Lemma

(49)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

For every regular language L there exists a constant p (that depends on L)

such that

for every string w∈L of length greater than p, there exists aninfinite family of stringsbelonging to L.

Why?Think:Regular expressions, DFAsFormalize our intuition! If L is a regular language, then

there exists a constant (pumping length) p such that for every string w∈L s.t.|w| ≥p

there exists a division of w in strings x,y,and z s.t. w=xyz such that 1. |y|>0,

2. |xy| ≤p, and

3. for all i≥0we have that xyⁱz∈L.

(50)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

For every regular language L there exists a constant p (that depends on L) such that

Why?Think:Regular expressions, DFAsFormalize our intuition! If L is a regular language, then

2. |xy| ≤p, and

(51)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

Why?

Think:Regular expressions, DFAsFormalize our intuition! If L is a regular language, then

2. |xy| ≤p, and

(52)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

Why?Think:Regular expressions, DFAs

Formalize our intuition! If L is a regular language, then

2. |xy| ≤p, and

(53)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

Why?Think:Regular expressions, DFAsFormalize our intuition!

If L is a regular language, then

2. |xy| ≤p, and

(54)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

Why?Think:Regular expressions, DFAsFormalize our intuition!

If L is a regular language, then

2. |xy| ≤p, and

(55)

A simple observation about DFA

start E O

0 1

computation start E

E

O

E

string .

.

. 0

1

0

computation E start

E

O

string .

.

. 0

0

1

(56)

A simple observation about DFA

Image source: Wikipedia

– LetA= (S,Σ, δ,s0,F)be a DFA.

– For every stringw∈Σ^∗of the length greater than or equal to the number of states ofA, i.e.|w| ≥ |S|, we have that

– the uniquecomputationofAonwre-visits at least one state after reading first|S|letters !

(57)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

If L is a regular language, then there exists a constant (pumping length) p such that for every string w∈L s.t.|w| ≥p there exists a division of w in strings x,y, and z s.t. w=xyz such that

1. |y|>0, 2. |xy| ≤p, and

– LetAbe the DFA acceptingLandpbe the set of states inA. – Letw= (a1a2. . .ak)∈Lbe any string of length≥p.

– Lets0a1s1a2s2. . .akskbe the run ofwonA.

– Consider firstn+1 states—at least one state must occur twice. – Letibe the index of first state that the run revisits and letjbe the

index of second occurrence of that state, i.e.si=sj,

– Letx=a1a2. . .ai−1andy=aiai+1. . .aj−1, andz=ajaj+1. . .ak. – notice that|y|>0 and|xy| ≤n

– Also, notice that for alli≥0 the stringxyⁱzis also inL.

(58)

Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

If L is a regular language, then there exists a constant (pumping length) p such that for every string w∈L s.t.|w| ≥p there exists a division of w in strings x,y, and z s.t. w=xyz such that

1. |y|>0, 2. |xy| ≤p, and

– LetAbe the DFA acceptingLandpbe the set of states inA.

– Letw= (a1a2. . .ak)∈Lbe any string of length≥p.

– Lets0a1s1a2s2. . .akskbe the run ofwonA.

– Consider firstn+1 states—at least one state must occur twice.

– Letibe the index of first state that the run revisits and letjbe the index of second occurrence of that state, i.e.si=sj,

– Letx=a1a2. . .ai−1andy=aiai+1. . .aj−1, andz=ajaj+1. . .ak. – notice that|y|>0 and|xy| ≤n

– Also, notice that for alli≥0 the stringxyⁱzis also inL.

(59)

Applying Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

L∈Σ^∗is aregularlanguage

=⇒

there existsp≥1such that

for allstrings w∈L with|w| ≥p we have that

there existsx,y,z∈Σ^∗with w=xyz,|y|>0,|xy| ≤p such that for alli≥0we have that

xyⁱz∈L.

Pumping Lemma (Contrapositive)

For allp≥1we have that

there existsa string w∈L with|w| ≥p such that

for allx,y,z∈Σ^∗with w=xyz,|y|>0,|xy| ≤p we have that there existsi≥0such that

xyⁱz6∈L

=⇒

L∈Σ^∗is not aregularlanguage.

(60)

Applying Pumping Lemma

Theorem (Pumping Lemma for Regular Languages)

L∈Σ^∗is aregularlanguage

=⇒

there existsp≥1such that

for allstrings w∈L with|w| ≥p we have that

there existsx,y,z∈Σ^∗with w=xyz,|y|>0,|xy| ≤p such that for alli≥0we have that

xyⁱz∈L.

Pumping Lemma (Contrapositive)

For allp≥1we have that

there existsa string w∈L with|w| ≥p such that

for allx,y,z∈Σ^∗with w=xyz,|y|>0,|xy| ≤p we have that there existsi≥0such that

xyⁱz6∈L

=⇒

L∈Σ^∗is not aregularlanguage.

(61)

Applying Pumping Lemma

How to show that a languageLis non-regular.

1. Letpbe an arbitrary number (pumping length).

2. (Cleverly) Find arepresentativestringwofLof size≥p.

3. Try out all ways to break the string intoxyztriplet satisfying that

|y|>0 and|xy| ≤n. If the step 3 was clever enough, there will be finitely many cases to consider.

4. For every triplet show that for someithe stringxyⁱzis not inL, and hence it yields contradiction with pumping lemma.

(62)

Applying Pumping Lemma

Theorem

Prove that the language L={0ⁿ1ⁿ}is not regular.

Proof.

1. State the contrapositive of Pumping lemma. 2. Letpbe an arbitrary number.

3. Consider the string 0^p1^p ∈L. Notice that|0^p1^p| ≥p.

4. Only way to break this string inxyztriplets such that|xy| ≤pand y6=εis to choosey=0^kfor some 1≤k≤p.

5. For each such triplet, there exists ani(sayi=0) such thatxyⁱz6∈L. 6. HenceLis non-regular.

(63)

Applying Pumping Lemma

Theorem

Proof.

1. State the contrapositive of Pumping lemma.

2. Letpbe an arbitrary number.

(64)

Applying Pumping Lemma

Theorem

Proof.

(65)

Applying Pumping Lemma

Theorem

Proof.

5. For each such triplet, there exists ani(sayi=0) such thatxyⁱz6∈L.

6. HenceLis non-regular.

(66)

Proving a language Regular

Proving Regularity

Pumping Lemma is necessary but not sufficient condition for regularity.

Consider the language

L={#aⁿbⁿ : n≥1} ∪ {#^kw : k6=1,w∈ {a,b}^∗}. Verify that this language satisfies the pumping condition, but is not regular!

(67)

Proving a language Regular

Proving Regularity

Pumping Lemma is necessary but not sufficient condition for regularity.

Consider the language

L={#aⁿbⁿ : n≥1} ∪ {#^kw : k6=1,w∈ {a,b}^∗}.

Verify that this language satisfies the pumping condition, but is not regular!