TOC Chapter 5

Chapter 5. Finite State Automata with Output and Minimization

In this chapter, we consider Myhill-Nerode theorem, minimization of deterministic finite state automaton (DFSA) and finite state automaton (FSA) with output.

5.1. Myhill-Nerode Theorem

In an earlier chapter, we considered the examples of serial adder, parity machine, acceptor accepting {aⁿb^m|n,m ≥ 1}, and many more such examples. Consider the serial adder. After getting some input, the machine can be in ‘carry’ state or ‘no carry’ state. It does not matter what exactly the earlier input was. It is only necessary to know whether it has produced a carry or not. Hence, the FSA need not distinguish between each and every input. It distinguishes between classes of inputs. In the above case, the whole set of inputs can be partitioned into two classes – one that produces a carry and another that does not produce a carry. Similarly, in the case of parity checker, the machine distinguishes between two classes of input strings: those containing odd number of 1’s and those containing even number of 1’s. Thus, the FSA distinguishes between classes of input strings. These classes are also finite. Hence, we say that the FSA has finite amount of memory.

Theorem 5.1 (Myhill-Nerode) The following three statements are equivalent. L ⊆ Σ* is accepted by a DFSA. L is the union of some of the equivalence classes of a right invariant equivalence relation of finite index on Σ*. Let equivalence relation RL be defined over Σ* as follows: xRL y if and only if, for all z ∊ Σ*, xz is in L exactly when yz is in L. Then RL is of finite index. Proof We shall prove (1) ⇒ (2), (2) ⇒ (3), and (3) ⇒ (1). (1) ⇒ (2) Let L be accepted by a FSA M = (K, Σ, δ, q0, F). Define a relation RM on Σ* such that xRMy if δ(q0, x) = δ(q0,y). RM is an equivalence relation, as seen below. ∀x xRMx, since δ(q0, x) = δ(q0, x), ∀x xRMy ⇒ yRMx ∵ δ(q0, x) = δ(q0, y) which means δ(q0, y) = δ(q0, x), ∀x, y xRM y and yRMz ⇒ xRMz. For if δ(q0, x) = δ(q0, y) and δ(q0, y) = δ(q0, z) then δ(q0, x) = δ(q0, z). So RM divides Σ* into equivalence classes. The set of strings which take the machine from q0 to a particular state qi are in one equivalence class. The number of equivalence classes is therefore equivalent to the number of states of M, assuming every state is reachable from q0. (If a state is not reachable from q0, it can be removed without affecting the language accepted). It can be easily seen that this equivalence relation RM is right invariant, i.e., if xRM y, xzRM yz ∀z ∊ Σ*. δ(q0, x) = δ (q0, y) if xRM y, δ(q0, xz) = δ(δ (q0, x), z) = δ(δ (q0, y), z) = δ(q0, yz). Therefore xzRM yz. L is the union of those equivalence classes of RM which correspond to final states of M. (2) ⇒ (3) Assume statement (2) of the theorem and let E be the equivalence relation considered. Let RL be defined as in the statement of the theorem. We see that xEy ⇒ xRL y. If xEy, then xzEyz for each z ∊ Σ*. xz and yz are in the same equivalence class of E. Hence, xz and yz are both in L or both not in L as L is the union of some of the equivalence classes of E. Hence xRL y. Hence, any equivalence class of E is completely contained in an equivalence class of RL. Therefore, E is a refinement of RL and so the index of RL is less than or equal to the index of E and hence finite. (3) ⇒ (1) First, we show RL is right invariant. xRL y if ∀z in Σ*, xz is in L exactly when yz is in L or we can also write this in the following way: xRL y if for all w, z in Σ*, xwz is in L exactly when ywz is in L. If this holds xwRLyw. Therefore, RL is right invariant. Let [x] denote the equivalence class of RL to which x belongs. Construct a DFSA ML = (K′, Σ, δ′, q0, F′) as follows: K′ contains one state corresponding to each equivalence class of RL. [ε] corresponds to q′0. F′ corresponds to those states [x], x ∊ L. δ′ is defined as follows: δ′ ([x], a) = [xa]. This definition is consistent as RL is right invariant. Suppose x and y belong to the same equivalence class of RL. Then, xa and ya will belong to the same equivalence class of RL. For, δ′([x], a) = δ′([y], a) ⇓   ⇓ [xa] = [ya] if x ∊ L, [x] is a final state in M′, i.e., [x] ∊ F′. This automaton M′ accepts L.

5.2. Finite Automata with Output

Earlier we considered finite state automata with output like the serial adder. We now consider them formally. The output function can be defined in two ways. If it depends on the state alone, the machine is called a Moore machine. If it depends on both the states and the input, it is called a Mealy machine.

Definition 5.1 Let M = (K, Σ, Δ, δ, λ, q0) be a Moore FSA. Here: K is a finite set of states Σ is a finite set of input alphabet Δ is a finite set of output alphabet δ, the transition function, is a mapping : K × Σ → K λ, the output function, is a mapping : K → Δ q0 in K is the initial state. Since, we are interested in the output for an input, we do not specify any final state. Given an input a1a2 ... an, the machine starts in state q0, outputs b0, reads a1 and goes to q1 and outputs b1, reads a2 and outputs b2 by going to q2... and so on. Input: a1a2 ... an States: q0q1q2 ... qn Output: b0b1b2 ... bn So the output is b0b1 ... bn. It should be noted that for an input of length n, we get an output of length n + 1.

Problems and Solutions

1.	Show that {aibj|i, j ≤ 1, i ≠ j} is not regular.
Solution.	As in Example 5.3 am ≈ an m ≠ n ambn ≈ anbn ambn ∊ L but anbn ∉ L Therefore, we have a contradiction and the language is not regular.
2.	Which of the following languages are regular sets? Prove your answer. L1 = {xxR|x ∊ {0, 1}+} L2 = {xwxR|x,w ∊ {0, 1}+} L3 = {xxRw|x,w ∊ {0, 1}+}
Solution.	L1 is not regular. Suppose L1 is regular. Let n be the constant of the pumping lemma. Consider 0n110n. The pump will occur in the first n 0’s. So, we shall get strings 0m 110n ∊ L, m ≠ n which is a contradiction. L2 is regular. L2 can be represented by the regular expression 0(0 + 1)+ 0 + 1(0 + 1)+ 1. L3 is not regular. Suppose L3 is regular, (01)n(10)n0 ∊ L. x = (01)n, w = 0. By Myhill-Nerode theorem, since the number of equivalence classes is finite. (01), (01)2, (01)3,... all cannot belong to different equivalence classes. For some m and n, m ≠ n (01)m and (01)n will belong to the same equivalence class. We write this as (01)m ≈ (01)n. Let m < n. Because of the right invariance, (01)m(10)m0 ≈ (01)n(10)m0. Since (01)m(10)m0 ∊ L3, we conclude (01)n(10)m0 ∊ L3. But (01)n(10)m0 is not of the form xxRw. Hence, we arrive at a contradiction. Therefore, L3 is not regular.
3.	Construct a Mealy machine with Σ = Δ = {0, 1}. The output is 1 whenever the last four symbols read are 1111. Overlapping sequences are accepted. Output is 0 otherwise.
Solution.	Figure 5.12. Solution to Problem 3
4.	Use Myhill-Nerode theorem to show the following language is not regular {0i1j |gcd(i, j) = 1}
Solution.	L = {0i1j | gcd(i, j) = 1} is not regular. Suppose L is regular. Consider the sets of primes {p1, p2, ... .}. This is an infinite set. Consider the set of strings 0P1, 0P2, 0P3,... . By Myhill-Nerode theorem, all of them cannot be in different equivalence classes. For some pi and pj, 0Pi and 0Pj must be in the same equivalence class. 0Pi ≈ 0Pj 0Pi1Pj ≈ 0Pj1Pj 0Pi1Pj ∊ L whereas 0Pj1Pj ∉ L. Hence, we have a contradiction. L is not regular.
5.	Minimize the following DFSA. Indicate clearly which equivalence class corresponds to each state of the new automaton.     a b → 1 6 3   2 5 6   4 5   3 2   5 2 1   6 1 4
Solution.	Splitting into non-final and final states , . Considering b successors of 1,2,5,6 is split into . Further split is not possible. Hence, minimum state automaton is:     a b   → A A B A corresponds to {1, 6}.   B C B corresponds to {3, 4}.   C C A C corresponds to {2, 5}.

Exercises 1. Construct a Moore machine with input alphabet Σ = {0, 1}. The output after reading a string x is the reminder when x, the number whose binary representation is x is divided by 3. Hence, the output alphabet Δ = {0, 1, 2} leading 0’s in x in the binary representation of x is allowed. 2. Construct a Mealy machine with Σ = Δ = {0, 1}. The output is 1 whenever the last five input symbols contain exactly three 1’s and the 4th and 5th last symbols read are 11. After each substring which starts with two 1’s, analysis of the next string will not start until the end of this substring of length five, whether at the end 0 or 1 is output. For example, for input 11110100, output is 00000000. For input 11100110, the output is 00001000. 3. Find a Mealy machine with Σ = Δ = {0, 1} satisfying the following condition. The output at time t is 1 if the input at time t is the same as input at time t − 2. 4. Find a Mealy machine with Σ = Δ = {0, 1} satisfying the following condition: For every input subsequence x3i+1x3i+2x3i+3 the output is x3i+3 if this substring consisted of 2 or 3 1’s. Otherwise it is 0. 5. Find a Mealy machine with Σ = {a, b, c, d, e} and Δ = {0, 1} satisfying the following condition. The output is 1 if the last three symbols read are in alphabetical order i.e., abc, bcd or cde. Otherwise it is 0. 6. Use Myhill-Nerode theorem to show the following languages are not regular. {anbcn|n ≥ 1} {anbncn|n ≥ 1} {anbn2|n ≥ 1} (ww|w ∊ {0, 1}+} {anbm|n ≤ m, n, m ≥ 1} 7. Minimize the following DFSA. Indicate clearly which equivalence class corresponds to each state of the new automaton.     a b → 1 2 3   2 5 6   1 4   6 3   5 2 1   6 5 4 8. Given the following DFSAs. Construct minimum state DFSAs equivalent to them (Figure 5.13). Figure 5.13. State diagrams of DFSA in Exercise 8 9. Given two DFSAs, M1 and M2 (Figure 5.14). Prove that they are either equivalent or not equivalent. Figure 5.14. State diagrams of DFSA in Exercise 9 [View full size image] 10. Using pumping lemma or Myhill-Nerode theorem show that the following languages are not regular. L1 = {www|w ε {a, b}*} L2 = {a2n|n ≥ 0} L3 = {w|w has equal number of 0’s and 1’s} L4 = {x ε {a, b, c}*| length of x is a square}. 11. Given a language L accepted by a DFSA, M1 the minimal DFSA accepting L and another machine M2 for which L(M2) = L, prove that the number of non-final states in the minimal machine M1 must be less than or equal to the number of non-final states in M2.