Properties of Regular Languagues

Finite Automata and Formal Languages

TMV026/DIT321 LP4 2010 Lecture 9 April 27th 2010

Testing Equivalence of Regular Languages

There is no simple algorithm for testing this. We have seen how one can prove that 2 RE are equal, hence the languages they represent are equivalent, but this is not an easy process. We will see now how to test when 2 DFA describe the same language.

Overview of todays lecture: Equivalence of Regular Languages Minimisation of Automata

Lecture 9 Properties of Regular Languagues

April 27th 2010 Ana Bove

Slide 1

Properties of Regular Languagues

Testing Equivalence of States in DFA

We shall rst answer the question: do states p and q behave in the same way?

Table-Filling Algorithm
This algorithm nds pairs of states that are distinguishable. Then, any pair of states that we do not nd distinguishable are equivalent.

Denition: We say that states p and q are equivalent if for all w, (p, w) is an accepting state i (q, w) is an accepting state.

Let D = (Q, , , q0 , F ) be a DFA. The algorithm is as follows: Basis: If p is an accepting state and q is not, the (p, q) are distinguishable. Inductive step: Let p and q be states such that for some symbol a, (p, a) = r and (q, a) = s with the pair (r, s) known to be distinguishable. Then (p, q) are also distinguishable. (If w distinguishes r and s then aw must distinguish p and q since (p, aw) = (r, w) and (q, aw) = (s, w).)
Lecture 9
April 27th 2010 Ana Bove

Note: We do not require that (p, w) = (q, w).

Denition: If p and q are not equivalent, then they are distinguishable.

That is, there exists at least one w is that one of (p, w) and (q, w) is an accepting state and the other is not.

Lecture 9

April 27th 2010 Ana Bove

Slide 2

Slide 3

Properties of Regular Languagues

Properties of Regular Languagues

Example: Table-Filling Algorithm

For the following DFA, we ll to table with an X at distinguishable pairs. a q0 q1 q2 q3 q4 q5 q1 q3 q4 q5 q5 q5 b q2 q4 q3 q5 q5 q5 q5 q4 q3 q2 q1 q0 X X X X X q1 X X X q2 X X X q3 X q4 X

Example: Table-Filling Algorithm

For the following DFA, we ll to table with an X at distinguishable pairs. a q0 q1 q2 q3 q4 q5 q1 q2 q3 q4 q5 q0 q5 q4 q3 q2 q1 X X q0 X X X X q1 X X X q2 q3 X X q4 X

Let us consider the base case of the algorithm. Let us consider the pair (q0 , q4 ). Let us consider the pair (q0 , q3 ). Finally, let us consider the pairs (q3 , q4 ) and (q1 , q2 ).
Lecture 9
April 27th 2010 Ana Bove

Let us consider the base case of the algorithm. Let us consider the pair (q0 , q5 ). Let us consider the pair (q0 , q2 ). We go on with the remaining pairs.
Slide 4 Lecture 9
April 27th 2010 Ana Bove

Slide 5

Properties of Regular Languagues

Properties of Regular Languagues

Equivalent States Theorem: Let D = (Q, , , q0 , F ) be a DFA. If 2 states are not

distinguishable by the table-lling algorithm then the states are equivalent.

Testing Equivalence of Regular Languages

We can use the table-lling algorithm to test equivalence of regular languages. Let L and M be 2 regular languages. Let DL = (QL , , L , qL , FL ) and DM = (QM , , M , qM , FM ) be their corresponding DFA. Let us assume QL QM = (easy to obtain by renaming). We proceed now as follows. Construct D = (QL QM , , , , FL FM ). (The initial state is irrelevant.) is the union of L and M as a function. One should now check if the pair (qL , qM ) is equivalent. If so, a string is accepted by DL i it is accepted by DM . Hence L and M are equivalent languages.
Lecture 9
April 27th 2010 Ana Bove

Proof: Let us assume there is a bad pair (p, q) such that p and q are
distinguishable but the table-lling algorithm doesnt nd them so. If there are bad pairs, let (p , q ) be a bad pair with the shortest string w = a1 a2 . . . an that distinguishes 2 states. Observe w is not otherwise (p , q ) are found distinguishable in the base step. Let (p , a1 ) = r and (q , a1 ) = s. States r and s are distinguished by a2 . . . an since this string takes r to (p , w) and s to (q , w). Now string a2 . . . an distinguishes 2 states and is shorter than w which is the shortest string that distinguishes a bad pair. Then (r, s) cannot be a bad pair and hence it must be found distinguishable by the algorithm. Then the inductive part should have found (p , q ) distinguishable. This contradict the assumption that bad pairs exist.
Lecture 9
April 27th 2010 Ana Bove

Slide 6

Slide 7

Properties of Regular Languagues

Properties of Regular Languagues

Equivalent Relations
(Recall from Set theory.) (Recall from Set theory.)

Partitions

Denition: A relation R over a set S that is reexive, symmetric and

transitive is called an equivalence relation over S. In mathematical notation: R S S is an equivalence relation i R is Reexive: a S, aRa Symmetric: a, b S, aRb bRa Transitive: a, b, c S, aRb bRc aRc

Denition: A set P is a partition over the set S if:

Every element of P is a non-empty subset of S C P, C = C S Elements of P are pairwise disjoint C1 , C2 P, C1 = C2 C1 C2 = The union of the elements of P is equal to S C=S
CP

Note: Alternative notations: (a, b) R, R(a, b), (a, b) satises R.

Lecture 9
April 27th 2010 Ana Bove

Slide 8

Lecture 9

April 27th 2010 Ana Bove

Slide 9

Properties of Regular Languagues

Properties of Regular Languagues

Equivalent Classes
(Recall from Set theory.) Let R be an equivalent relation over S.

Example: Equivalent Classes

(Recall from Set theory.) Let S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Let the relation x y be dened as 3 divides x y. It can be proved that is an equivalent relation. The quotient S/ consist of the following classes: [1] = {1, 4, 7, 10} [2] = {2, 5, 8} [3] = {3, 6, 9}

Denition: If a S, then the equivalent class of a in S is the set dened

as [a] = {b S | aRb}.

Lemma: a, b S, [a] = [b] i aRb. Theorem: The set of all equivalence classes in S with respect to R form a partition over S. Note: This partition is called the quotient and is denoted as S/R.
Lecture 9
April 27th 2010 Ana Bove

Slide 10

Lecture 9

April 27th 2010 Ana Bove

Slide 11

Properties of Regular Languagues

Properties of Regular Languagues

Equivalence of States: An Equivalence Relation

The relation state p is equivalent to state q, which we shall denote p q, is an equivalence relation. (Prove it as an exercise!) Reexive: every state p is equivalent to itself p, p p Symmetric: for any states p and q, if p is equivalent to q then q is equivalent to p p q, p q q p Transitive: for any states p, q and r, if p is equivalent to q and q is equivalent to r then p is equivalent to r. p q r, p q q r p r (See Theorem 4.23 for a proof of the transitivity part.)
Lecture 9
April 27th 2010 Ana Bove

Partition of States
Let D = (Q, , , q0 , F ) be a DFA. The table-lling algorithm denes the equivalence of states relation over Q. Since this is an equivalence relation we can dene the quotient Q/ . This quotient gives us a partition of the states into classes/blocks of mutually equivalent states.

Example: The partition for the example in slide 4 is the following (note
the singleton classes!) {q0 } {q1 , q2 } {q3 , q4 } {q5 }

Example: The partition for the example in slide 5 is the following

{q0 , q3 } {q1 , q4 } {q2 , q5 }

Note: Classes might also have more than 2 elements.

Slide 12 Lecture 9
April 27th 2010 Ana Bove

Slide 13

Properties of Regular Languagues

Properties of Regular Languagues

Minimisation of DFA
Let D = (Q, , , q0 , F ) be a DFA. Q/ allows to build an equivalent DFA with the minimum number of states. In addition, this minimum DFA is unique (modulo the name of the states).
The algorithm for building the minimum DFA D = (Q , , , q0 , F ) is:

Examples Example: The minimal DFA corresponding to the DFA in slide 4 is

a, b q0 a, b q1 , q2 a, b q3 , q4 a, b q5

1. Eliminate any non accessible state 2. Partition the remaining states with the help of the table-lling algorithm 3. Use each block as a single state in the new DFA 4. The start state is the block containing q0 , the nal states are all those blocks containing elements in F 5. (S, a) = T if given any q S, (q, a) = p for some p T (Actually, the partition guarantees that q S, p T, (q, a) = p)
Lecture 9
April 27th 2010 Ana Bove

Example: The minimal DFA corresponding to the DFA in slide 5 is

a q0 , q3 a q1 , q4 a q2 , q5

Slide 14

Lecture 9

April 27th 2010 Ana Bove

Slide 15

Properties of Regular Languagues

Properties of Regular Languagues

Does the Minimisation Algorithm Give a Minimal DFA?

Given a DFA D, the minimisation algorithm gives us a DFA D with the minimal number of states with respect to those of D. Can you see why? But, could there exist a DFA A completely unrelated to D, also accepting the same language and with less states than those in D ? Section 4.4.4 in the book shows by contradiction that A cannot exist.

Can we Minimise a NFA?

One can of course nd (in some cases) an smaller NFA, but the algorithm we presented before does not do the job. 0, 1

Example: Consider the following NFA

q0 1 q2 0

q1

The table-lling algorithm does not nd equivalent states in this case. However, the following is a smaller and equivalent NFA for the language. 0, 1

minimisation algorithm described before, then D has as few states as any DFA equivalent to D.

Theorem: If D is a DFA and D the DFA constructed from D with the

q0
Lecture 9

q1
Slide 17

Lecture 9

April 27th 2010 Ana Bove

Slide 16

April 27th 2010 Ana Bove

Properties of Regular Languagues

Properties of Regular Languagues

Functional Representation of the Minimisation Algorithm

data Q = ... deriving (Eq, Show) data S = ... delta :: Q -> S -> Q final :: Q -> Bool

Func. Representation of the Minimisation Alg. (Cont.)

-- swaps elements in a pair swap :: (a,a) -> (a,a) swap (p,q) = (q,p) -- equality in pairs: order doesnt matter here pair_eq :: Eq a => (a,a) -> (a,a) -> Bool pair_eq p q = p == q || p == swap q -- remove "repetition" from the list clean :: Eq a => [(a,a)] -> [(a,a)] clean = nubBy pair_eq -- maps a function to the elements of the pair map_pair :: (a -> b -> c) -> (a,a) -> b -> (c,c) map_pair f (p,q) x = (f p x, f q x)

-- lists with all states and all the symbols states :: [Q] states = [...] alphabet :: [S] alphabet = [...]
Lecture 9
April 27th 2010 Ana Bove

Slide 18

Lecture 9

April 27th 2010 Ana Bove

Slide 19

Properties of Regular Languagues

Properties of Regular Languagues

Func. Representation of the Minimisation Alg. (Cont.)

-- all possible pairs of states without repetition all_pairs :: [(Q,Q)] all_pairs = [ (p,q) | p <- states, q <- states, p /= q]

Func. Representation of the Minimisation Alg. (Cont.)

-- equiv ss pps dds gives the equivalent states -- ss are all the symbols in the alphabet -- pps are the pairs of states still to check if distinguishable -- dds are all pairs of states already found distinguishable equiv :: [S] -> [(Q,Q)] -> [(Q,Q)] -> [(Q,Q)] equiv ss pps dds = let dqs = [ pq | pq <- pps, or (map (\pp -> elem pp dds) (map (map_pair delta pq) ss))] nds = union dds dqs nps = pps \\ dqs in if not (null dqs) then equiv ss nps nds else clean pps -- if we instead return (clean nds) we give all distinguishable pairs
Lecture 9
April 27th 2010 Ana Bove

-- tests to distinguish if one state is final but not the other dist :: (Q,Q) -> Bool dist (p,q) = final p && not(final q) || final q && not(final p)

-- splits a list according to whether the elem. satisfies dist splitBy :: [(Q,Q)] -> ([(Q,Q)],[(Q,Q)]) splitBy [] = ([],[]) splitBy (p:pps) = let (qs,ds) = splitBy pps in if dist p then (qs,p:ds) else (p:qs,ds)
Lecture 9
April 27th 2010 Ana Bove

Slide 20

Slide 21

Properties of Regular Languagues

Properties of Regular Languagues

Func. Representation of the Minimisation Alg. (Cont.)

-- group the pairs into classes group_classes :: Eq a => [(a,a)] -> [[a]] group_classes [] = [] group_classes ((p,q):pps) = let pqs = (p,q):[ pr | pr <- pps, (fst pr == p || fst pr == q || snd pr == p || snd pr == q)] nps = pps \\ pqs qs = nub ([fst p | p <- pqs] ++ [snd p | p <- pqs]) in qs : group_classes nps

Func. Representation of the Minimisation Alg. (Cont.)

-- add the add_singel add_singel add_singel add_singel classes with just one state :: Eq a => [a] -> [[a]] -> [[a]] [] pps = pps (q:qs) pps | or (map (elem q) pps) = add_singel qs pps (q:qs) pps = [q] : add_singel qs pps

-- gives the base case of the test-filling algorithm and the rest (rest,base_dist) = splitBy all_pairs -- returns all equivalent classes equiv_classes :: [[Q]] equiv_classes = add_singel states (group_classes (equiv alphabet rest base_dist))

Lecture 9

April 27th 2010 Ana Bove

Slide 22

Lecture 9

April 27th 2010 Ana Bove

Slide 23