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.
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
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 – 3 of 24
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)
Ashutosh Trivedi DFA Equivalence and Minimization
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)
Ashutosh Trivedi – 3 of 24
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)
Ashutosh Trivedi DFA Equivalence and Minimization
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.
Ashutosh Trivedi – 4 of 24
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.
Ashutosh Trivedi DFA Equivalence and Minimization
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.
Ashutosh Trivedi – 4 of 24
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.
Ashutosh Trivedi DFA Equivalence and Minimization
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.
Ashutosh Trivedi – 4 of 24
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.
Ashutosh Trivedi DFA Equivalence and Minimization
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx. – if(p0,q0)were discovered by table-filling algorithm and(p,q)must have
been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi – 5 of 24
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx. – if(p0,q0)were discovered by table-filling algorithm and(p,q)must have
been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi DFA Equivalence and Minimization
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx. – if(p0,q0)were discovered by table-filling algorithm and(p,q)must have
been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi – 5 of 24
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx. – if(p0,q0)were discovered by table-filling algorithm and(p,q)must have
been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi DFA Equivalence and Minimization
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx. – if(p0,q0)were discovered by table-filling algorithm and(p,q)must have
been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi – 5 of 24
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx.
– if(p0,q0)were discovered by table-filling algorithm and(p,q)must have been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi DFA Equivalence and Minimization
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx.
– if(p0,q0)were discovered by table-filling algorithm and(p,q)must have been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi – 5 of 24
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.
– Thenp0=δ(p,a)andq0=δ(q,a)are also distinguished by stringx.
– if(p0,q0)were discovered by table-filling algorithm and(p,q)must have been discovered as well.
– If(p0,q0)were not discovered by table-filling algorithm, then(p0,q0)is a bad pair with a shorter distinguishing string.
Ashutosh Trivedi DFA Equivalence and Minimization
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≡= (Q0,Σ0, δ0,q00,F0), calledQuotient Automata, where
– Q0={[q] : q∈Q}, – Σ0= Σ,
– δ0([q],a) =δ(q,a)for alla∈Σ, – q00= [q0], and
– F0={[q] : q∈F}.
Theorem
A≡is the minimum and unique (up to state renaming) DFA equivalent to A.
Ashutosh Trivedi – 6 of 24
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≡= (Q0,Σ0, δ0,q00,F0), calledQuotient Automata, where
– Q0={[q] : q∈Q}, – Σ0= Σ,
– δ0([q],a) =δ(q,a)for alla∈Σ, – q00= [q0], and
– F0={[q] : q∈F}.
Theorem
A≡is the minimum and unique (up to state renaming) DFA equivalent to A.
Ashutosh Trivedi DFA Equivalence and Minimization
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≡= (Q0,Σ0, δ0,q00,F0), calledQuotient Automata, where
– Q0={[q] : q∈Q}, – Σ0= Σ,
– δ0([q],a) =δ(q,a)for alla∈Σ, – q00= [q0], and
– F0={[q] : q∈F}.
Theorem
A≡is the minimum and unique (up to state renaming) DFA equivalent to A.
Ashutosh Trivedi – 7 of 24
Proof of Minimality
Theorem
A≡is the minimum and unique (up to state renaming) DFA equivalent to A.
Proof.
– The proof is by contradiction.
– 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.
Ashutosh Trivedi DFA Equivalence and Minimization
DFA Equivalence and Minimization
Myhill-Nerode Theorem
Pumping Lemma
Ashutosh Trivedi – 9 of 24
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?
Ashutosh Trivedi DFA Equivalence and Minimization
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.
Ashutosh Trivedi – 10 of 24
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.
Ashutosh Trivedi DFA Equivalence and Minimization
Myhill-Nerode Theorem
Theorem (Myhill-Nerode Theorem)
A language L is regular if and only if there exists a string-equivalence relation≡L with finitely many classes.
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?
Ashutosh Trivedi – 11 of 24
Myhill-Nerode Theorem
Theorem (Myhill-Nerode Theorem)
A language L is regular if and only if there exists a string-equivalence relation≡L with finitely many classes.
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?
Ashutosh Trivedi DFA Equivalence and Minimization
Myhill-Nerode Theorem
Theorem (Myhill-Nerode Theorem)
A language L is regular if and only if there exists a string-equivalence relation≡L with finitely many classes.
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?
Ashutosh Trivedi – 11 of 24
Myhill-Nerode Theorem
Theorem (Myhill-Nerode Theorem)
A language L is regular if and only if there exists a string-equivalence relation≡L with finitely many classes.
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?
Ashutosh Trivedi DFA Equivalence and Minimization
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.
Ashutosh Trivedi – 12 of 24
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.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : 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, . . . ,0i, . . .}.
5. It must be the case that some two string 0mand 0n, withm6=nare mapped to same equivalence class.
6. It implies that for all stringsw∈Σ∗we have that 0m.w∈Liff 0n.w∈L. 7. However, 0m1m∈Lbut 0n1m6∈L, a contradiction.
8. HenceLis not regular.
Ashutosh Trivedi – 13 of 24
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : 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, . . . ,0i, . . .}.
5. It must be the case that some two string 0mand 0n, withm6=nare mapped to same equivalence class.
6. It implies that for all stringsw∈Σ∗we have that 0m.w∈Liff 0n.w∈L. 7. However, 0m1m∈Lbut 0n1m6∈L, a contradiction.
8. HenceLis not regular.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : 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, . . . ,0i, . . .}.
5. It must be the case that some two string 0mand 0n, withm6=nare mapped to same equivalence class.
6. It implies that for all stringsw∈Σ∗we have that 0m.w∈Liff 0n.w∈L. 7. However, 0m1m∈Lbut 0n1m6∈L, a contradiction.
8. HenceLis not regular.
Ashutosh Trivedi – 13 of 24
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : 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, . . . ,0i, . . .}.
5. It must be the case that some two string 0mand 0n, withm6=nare mapped to same equivalence class.
6. It implies that for all stringsw∈Σ∗we have that 0m.w∈Liff 0n.w∈L. 7. However, 0m1m∈Lbut 0n1m6∈L, a contradiction.
8. HenceLis not regular.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : 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, . . . ,0i, . . .}.
5. It must be the case that some two string 0mand 0n, withm6=nare mapped to same equivalence class.
6. It implies that for all stringsw∈Σ∗we have that 0m.w∈Liff 0n.w∈L. 7. However, 0m1m∈Lbut 0n1m6∈L, a contradiction.
8. HenceLis not regular.
Ashutosh Trivedi – 13 of 24
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : 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, . . . ,0i, . . .}.
5. It must be the case that some two string 0mand 0n, withm6=nare mapped to same equivalence class.
6. It implies that for all stringsw∈Σ∗we have that 0m.w∈Liff 0n.w∈L.
7. However, 0m1m∈Lbut 0n1m6∈L, a contradiction. 8. HenceLis not regular.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : 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, . . . ,0i, . . .}.
5. It must be the case that some two string 0mand 0n, withm6=nare mapped to same equivalence class.
6. It implies that for all stringsw∈Σ∗we have that 0m.w∈Liff 0n.w∈L.
7. However, 0m1m∈Lbut 0n1m6∈L, a contradiction.
8. HenceLis not regular.
Ashutosh Trivedi – 14 of 24
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : n≥0}is not regular.
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={0i : i≥0}.
3. Since any two string inMare distinguishable with respect toL(i.e. 0m0n∈Lbut 0n1m6∈Lforn6=m), it follows from Myhill-Nerode theorem thatLis a non-regular language.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : n≥0}is not regular.
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={0i : i≥0}.
3. Since any two string inMare distinguishable with respect toL(i.e. 0m0n∈Lbut 0n1m6∈Lforn6=m), it follows from Myhill-Nerode theorem thatLis a non-regular language.
Ashutosh Trivedi – 14 of 24
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : n≥0}is not regular.
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={0i : i≥0}.
3. Since any two string inMare distinguishable with respect toL(i.e. 0m0n∈Lbut 0n1m6∈Lforn6=m), it follows from Myhill-Nerode theorem thatLis a non-regular language.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Myhill-Nerode Theorem
Theorem
The language L={0n1n : n≥0}is not regular.
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={0i : i≥0}.
3. Since any two string inMare distinguishable with respect toL(i.e.
0m0n∈Lbut 0n1m6∈Lforn6=m), it follows from Myhill-Nerode theorem thatLis a non-regular language.
Ashutosh Trivedi – 15 of 24
Some languages are not regular!
The following languages are regular or non-regular?
– The language{0n1n : 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{0i1j : i>j} – The language{0i1j : i≤j}
– The language of palindromes of{0,1}
Ashutosh Trivedi DFA Equivalence and Minimization
Some languages are not regular!
The following languages are regular or non-regular?
– The language{0n1n : 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{0i1j : i>j} – The language{0i1j : i≤j}
– The language of palindromes of{0,1}
Ashutosh Trivedi – 16 of 24
DFA Equivalence and Minimization
Myhill-Nerode Theorem
Pumping Lemma
Ashutosh Trivedi DFA Equivalence and Minimization
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 xyiz∈L.
Ashutosh Trivedi – 17 of 24
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 xyiz∈L.
Ashutosh Trivedi DFA Equivalence and Minimization
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 xyiz∈L.
Ashutosh Trivedi – 17 of 24
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, DFAs
Formalize 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 xyiz∈L.
Ashutosh Trivedi DFA Equivalence and Minimization
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 xyiz∈L.
Ashutosh Trivedi – 17 of 24
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 xyiz∈L.
Ashutosh Trivedi DFA Equivalence and Minimization
A simple observation about DFA
start E O
0 1
0 1
computation start E
E
O
E
string .
.
.
. 0
1
0
computation E start
E
E
O
string .
.
.
. 0
0
1
Ashutosh Trivedi – 19 of 24
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 !
Ashutosh Trivedi DFA Equivalence and Minimization
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
3. for all i≥0we have that xyiz∈L.
– 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 stringxyizis also inL.
Ashutosh Trivedi – 20 of 24
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
3. for all i≥0we have that xyiz∈L.
– 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 stringxyizis also inL.
Ashutosh Trivedi DFA Equivalence and Minimization
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
xyiz∈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
xyiz6∈L
=⇒
L∈Σ∗is not aregularlanguage.
Ashutosh Trivedi – 21 of 24
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
xyiz∈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
xyiz6∈L
=⇒
L∈Σ∗is not aregularlanguage.
Ashutosh Trivedi DFA Equivalence and Minimization
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 stringxyizis not inL, and hence it yields contradiction with pumping lemma.
Ashutosh Trivedi – 23 of 24
Applying Pumping Lemma
Theorem
Prove that the language L={0n1n}is not regular.
Proof.
1. State the contrapositive of Pumping lemma. 2. Letpbe an arbitrary number.
3. Consider the string 0p1p ∈L. Notice that|0p1p| ≥p.
4. Only way to break this string inxyztriplets such that|xy| ≤pand y6=εis to choosey=0kfor some 1≤k≤p.
5. For each such triplet, there exists ani(sayi=0) such thatxyiz6∈L. 6. HenceLis non-regular.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Pumping Lemma
Theorem
Prove that the language L={0n1n}is not regular.
Proof.
1. State the contrapositive of Pumping lemma.
2. Letpbe an arbitrary number.
3. Consider the string 0p1p ∈L. Notice that|0p1p| ≥p.
4. Only way to break this string inxyztriplets such that|xy| ≤pand y6=εis to choosey=0kfor some 1≤k≤p.
5. For each such triplet, there exists ani(sayi=0) such thatxyiz6∈L. 6. HenceLis non-regular.
Ashutosh Trivedi – 23 of 24
Applying Pumping Lemma
Theorem
Prove that the language L={0n1n}is not regular.
Proof.
1. State the contrapositive of Pumping lemma.
2. Letpbe an arbitrary number.
3. Consider the string 0p1p ∈L. Notice that|0p1p| ≥p.
4. Only way to break this string inxyztriplets such that|xy| ≤pand y6=εis to choosey=0kfor some 1≤k≤p.
5. For each such triplet, there exists ani(sayi=0) such thatxyiz6∈L. 6. HenceLis non-regular.
Ashutosh Trivedi DFA Equivalence and Minimization
Applying Pumping Lemma
Theorem
Prove that the language L={0n1n}is not regular.
Proof.
1. State the contrapositive of Pumping lemma.
2. Letpbe an arbitrary number.
3. Consider the string 0p1p ∈L. Notice that|0p1p| ≥p.
4. Only way to break this string inxyztriplets such that|xy| ≤pand y6=εis to choosey=0kfor some 1≤k≤p.
5. For each such triplet, there exists ani(sayi=0) such thatxyiz6∈L.
6. HenceLis non-regular.
Ashutosh Trivedi – 24 of 24
Proving a language Regular
Proving Regularity
Pumping Lemma is necessary but not sufficient condition for regularity.
Consider the language
L={#anbn : n≥1} ∪ {#kw : k6=1,w∈ {a,b}∗}. Verify that this language satisfies the pumping condition, but is not regular!
Ashutosh Trivedi DFA Equivalence and Minimization
Proving a language Regular
Proving Regularity
Pumping Lemma is necessary but not sufficient condition for regularity.
Consider the language
L={#anbn : n≥1} ∪ {#kw : k6=1,w∈ {a,b}∗}.
Verify that this language satisfies the pumping condition, but is not regular!