THE UNI VE RS I T Y OF MI CH I GAN INFORMATION SYSTEMS LABORATORY Department of Electrical Engineering College of Engineering Technical Report ISL-65-1 AN ANALYSIS OF ERRORS IN FINITE AUTOMATA Philip S. Dauber April - l965 This work was supported in part by Air Force Contract AF 30(602)-3546. Section 4 represents work done while the author was associated with the General Electric Research Laboratory, Schenectady, New York.

AGL-. Z t trK I IiSM s e

Abstract This paper studies errors in finite automata. An error is defined as a pair of states and errors are thenclassified according to their probability of being corrected (i.e., being taken into the same state). Various results are then given on the partitioning properties of a particular type of error called a finite error.

1. Introduction This problem arose from an attempt to make a general study of reliability in computer-like machines. The classic results of von Neumann (von Neumann, 1956), deal only with networks which do not have any feedback. Thus a malfunction only causes the network to be in the incorrect state for a fixed length of time. However, a malfunction in the general case with feedback can cause an error which persists forever. Fortunately, not all errors are of this type. Some errors are of the type that can persist only for a bounded time. Some, although they can persist infinitely long, have a probability of being corrected which approaches one as the tapes get longer, Thus "almost all" of the "long" tapes correct the error. This is the phenomenon which will be studied in this paper. It will be shown that errors of the latter type induce a partition on the set of states. The possibility of adding states to the machine in order to get a more reliable one will also be discussed. In the next section we will formalize the problem in terms of the theory of automata. 2. Formalization of the Problem In order to clarify the notation and to make the problem more formal, we will begin by defining a finite automaton and an error in a finite automaton.

Definition 2.1: A finite automaton M is a triple M = (M', ~, 6). M' is a finite set with elements m. (set of states); Z is a finite set with elements a. (input alphabet); 1 6 is a function from M' x. Z -M' (next state function). Later we will use M both to denote the finite automaton and its set of states. We will also extend 6 to Z, the set of sequences of symbols from ~, in the natural manner with sequences read from left to right. Definition 2.2: a. An error, E, in a finite automaton, M, is a pair of states (m.,m.). b. An error, (mi,mj), is corrected by a tape t ("tape" is synonymous with "sequence") if and only if 6(mi,t) = 6(m.,t). We can think of an error (mi,m.) as the situation, when due to a previous malfunction, the automaton is in state m. and should be in state mj., or is in state m. and should be in state mi. We can see from the definition of an error being corrected that these are both equivalent. In this work we will consider sequences being generated by a random source. We will say that a random source with output alphabet Z has property P if and only if it is stationary and there:is a number 4

k, greater than zero, such that the probability of the symbol a following an arbitrary sequence x is greater than ko Definition 2.3: Let S be a random source with property P and output symbols Z, and let M = (M, Z, 6) be a finite automaton driven by S. For an error E = (m.im.) we define the following: a. yr(mi,m.) = probability that (mi,m.) is corrected by a tape of length 2. b. Y (m.,m ) = lim y7(m.,m.) if the limit exists. It is easy to see that for any source S and any error (mi,m.), ~ S(m, m.) exists. Lemma 2.1 lim Y7 (mim) always exists. S S PROO~F: l l> y (mimm) > y (mi,m.). Since the limit of a monotonic PROOF:R0 1 I 7 1 7 bound sequence always exists, the theorem is proved. Q.E.D. Now let us consider the following classification of errors in a finite automaton M being driven by a source S as. above. Definition 2.4: An error E - (m.,m.) is n 3 a. definite if and only if there is an 2 such that y7(E) 1. b. finite is and only if yS(E) = 1. c. correctable if and only if yS(E) > 0. do non-correctable if and only if S (E) = 0.

3. Fundamental Results In this section we will derive some fundamental properties of errors and will show the connection between the concepts of correctable and finite errors. Theorem 3.1 If Y(ml,m2) = gl and Y(m2,m3) g2' then 1 gl - g2 > Y(',m3) (gl + g2) PROOF: Let TO be the set of tapes that do not correct (ml,m2) or (m2,m3); T1 be the set that corrects (ml,m2) or (m2,m3) but not both; T2 be the set that corrects (mlm2) and (m2,m3); and T3 be the set that corrects (ml,m3)o We know that TO, Tl, and T2 are mutually disjoint and that T2 C T3C T2 U TO. We will use Pr2(T) to mean the probability that a tape t of length 2 is in T. Therefore, we have g + g2 = lim (Pr2(Tl) + 2Pr2(T2)) lim Pr (Tl) + 2 lim Pr (T2). Q2-oo -Qoo But we also have for all 2, Pr (Tl) + Pr (T2) < 1. Therefore gl+ g2 < 1 + lim Pr (T2) <1 +g where g3 = Y(ml,m3). Hence g3 > gl + g2 - 1. Likewise, letting Tll be the set of tapes which correct (mlm2) and not (m2,m3), and T12 be the set which connects (m2,m3) and not (ml,m2), we have Y (mme) = Pr(T2) + Pr2(Tll) and 7Y(m2,m3) = Pr (T2) + Pr2(Tl2)o

Thus IY(ml'm2) - y(m2,m3) I = IPr(Tll) - Pr~(T12) I But IPr (Tll) - Pr (T12) < Pr (T) < 1 - (PrQ(TO) + Pr(T2)). Now taking limits as 2 goes to infinity, we get g g21 < - g g3 <1 - gl-g2 Q.E.D. Corollary 3.1 The set of finite errors in an automaton M driven by a source with property P induces a partition on the set of states. That is, there is a partition 11F on the states of M so that E = (mim.) is finite if and only if m. = m j(F ) PROOF: It is obvious that if y(mi,m) = 1, then y(mj,mi) = 1 by the symmetry of the definition of being corrected. Likewise, y(m.imi) = 1. Now by Theorem 3.1 we have that if y(mi,m.) = 1 and y(m.,mk) = 1, 1J then y(mi,mk) = 1. Hence, the finiteness relation is an equivalence relation and partitions the set of states. Q.E.D. Theorem 3.2 Let C M x M be the relation (mi,m.)cC if and only if (m.,m.) is a correctable error. Then an error E = (mi,m..) is finite if and only if (mi,mj)EC and for all tapes t, (b(mit), 6(mj,t))EC.

PROOF: If (mi,mj) is finite then obviously (mi,m.) is correctable. If there is a tape t such that (b(n.i,t), 6(m.,t)) is not correctable, then for all t' (6(m.,tt'), 3(m.,tt')) is not correctable. Hence, lg(t) (mi,m) < 1 - (k)lg( < 1 where lg(t) is the length of the tape t, and k is the constant greater than zero associated with the source. Therefore (mi,mj) is not a finite error. Conversely, let us assume that for all t (6(mi,t), b(mjt))cC. Let A = [(mkm) I for some t b(mi,t) = mk and b(mk,t) = mn}. Then, for each (mk,mk )~A, pick a t' which corrects (mi,m) Let p = k where r = max lg(t'). Then (mi.,m.) > 1 - (l-p)[2/r] where [2/r] is the greatest integer less than 2/r. Hence lim y7(mi,mj.) >1 - lim (l-p) ]/r] Since p > 0, we have y(m.imj) = 1. Q.E.D. From this theorem we can get some idea of the connection of C and iF. We can also see that since the concept of an error being corrected is not dependent upon a source, the property of it being finite is also independent of the source. (This is true only as long as we are only dealing with source with property P.) The next theorem is a stronger characterization of iF with respect to the relation C. Theorem 3o3 iF is the largest partition with the substitution property such that m. m. ) O # (m. mj)eC. 8 1

PROOF: Let Ec be a partition with the substitution property such that mi - m:j(r)? m (m ),m.) C. Then, if mi - mj (), (mi,m)cC. Also, since E has the substitution property, for all tapes t o(m.,t) -= (mj,t)(r) and, hence, (6(mi,t), 6(m.i,t))eC. But by Theorem 3~2, this means that m. - m. (F). Therefore i < FA Q.E.D. An immediate consequence of this theorem is a decomposition of the automaton as follows. Corollary 3.2 If M is a finite automaton with a finite partition tF' then F can be state behavior realized by a cascade connection of two automata M/IF and T, where all errors in T are finite, and M/jF has no finite errors. PROOF: By Theorem 3.3. cF is a partition with the substitution property. Hence, we know (Hartmanis, 1962) that we can decompose M into a cascade connection of two automata where the state of the front automaton distinguishes between blocks of the partition and the back machine distinguishes the elements of a single block. Q.E.D. Let us now look at an example in order to demonstrate these theorems. Let M = ((a,b,cd,e), (0,1t, b) where b is the mapping shown in Table Io 9

60 1 a b d b a d c a' b d b d Table I It is easy to show that C = ((a,d),(d,a), (b,c), (cb), (ea), (ae) (end), (de),(be), (e,b), (ce), (e,c), (a,a), (b,b), (c,c), (dd), (ee)) There are four equivalence relations with the substitution property contained in C. 1 ( = {a, b Ec, d, e) -2 = {a-d',, c, e) 3 -= (a, bc, d, e) ok - a(d, bc, e} The greatest one is c4. Thus the only finite errors are ((a,a), (b,b). (c,c), (dad), (ee), (ad), (dc), (bc), (c,b). Also using Theorem 3.3 we can get a simple proof of a special case of a theorem which was proved by Winograd (Winograd, 1964), and also in another context by Gilbert and Moore (Gilbert and Moore, 1959). Corollary 3.3 All errors in an automaton M are finite if and only if M has a reset tape. (A tape t is a reset tape if 8(mi.,t) is independent of m..) 10

PROOF: From Theorem 3.3 we get that all errors in an automaton M are finite if and only if all errors are correctable. Define a tape t = tl t2.. tk_1 (k = number of states of M) as follows: tl corrects (mlm2) ti+l corrects ( t(ml, t.), t(mi.+2,tl... ti))t If it is possible to construct such a t, then t is a reset sequence. It is not possible to construct such a tape if and only if for some i, (6(mi+2-,tl.. t), (mi, ti)) is not a correctable error. But then, this (6(ml, t1.. t.), (m., t)) is not finite. i (i+21 ti)) is not finite Hence we can construct t if and only if all the errors are finite. Q.E.D. Let us now look at another example to show the use of this theorem. Let M = ([a,b,c,d, (0,11, 6) where 6 is shown in Table II. 6i011 a b c b c d c d b Id d b Table II It is easy to see that all the errors are correctable. Hence -F = (a,b,c,d) and all errors are finite. Upon examination it can be seen that the tape 000 is a reset tape since b(mi,000) = d regardless of m.. ~1 ~~ 11 11

4. Errors in Expanded Automata* This section will discuss the possibility of adding states to a finite automaton so that the new automaton has, in some sense or another, better error properties and still is a realization of the original automaton. It will be shown that for one sense of better this is not possible and that the reduced automaton has the best error properties. We will use E(M) for M x M, the set of ordered pairs of states of M, and E(A) < E(B) for the concept, which has not been made precise yet, of the error properties of an automaton A being better than those of an automaton B. There are three properties which we intuitively require for a notion of < 1) It must be a source independent. 2) The comparison of errors in A and in B must be a total comparison. That is, every error in A must be compared to at least one error in B and vice-versa. 3) For any source, an error in A must have at least as high a probability of correction as that of those in B to which it is compared. We are thus led to the following definition which satisfies these three properties. *Part of the work reported in this section was done while the author was associated with General Electric Research Laboratories Schenectady, New York, and was reported in GE Laboratory Report 64-RL-3826 E, December 1964o 12

Definition 4.1: Let A = (M1, ~, 51) and B = (M2, Z, b2) be two finite automata with the same input alphabet. We will say errors in A are less than errors in B, E(A) < E(B), if and only if there is a mapping of pairs of states of B onto pairs of states of A, h: M2 x M2-M1 x M1 onto, with the property that if (mi,mj) E M2 x M2 is corrected by a tape t, then t also corrects h(mi,mj) E M1 x M1. We can see that the definition fits our intuitive notion of the set of errors in one automaton being better than the set of errors in another since for any source S if y(mimj) = then y(h(mi,mj)) > c. Thus, h takes finite errors into finite errors and correctable errors into correctable errors. Also, h assigns to each error in A at least one error in B with the same or a lower probability of being corrected for any source. We should note at this point that the relation < is not an ordering on the set of finite automata. As an example of two automata which are not isomorphic and yet for which both E(A) < E(B) and E(B) < E(A), let A be the two input, mod 4 clock and let B be the two input, mod 4 counter of ones. The two are not isomprphic and yet since all the errors in both are not correctable and they both have the same number of errors, E(A) < E(B) and E(B) < E(A). We will now show some of the properties of this relation. Lemma 4.1 If M1 is a submachine of M2, then E(M1) < E(M2). 13

PROOF: Let h be the identity mapping on M x and let it map all other pairs in M x M2 into (mlgml), ml E My Now if (mimj) C M1 x M1i then the set of tapes which correct it in M1 is the same as the set of tapes which correct it in M2. However, if (mi,mj) is not in M1 x Ml, then h(mimj) = (mlml) and is thus corrected by all tapes. Therefore h has the desired properties. QoE.Do Lemma 4.2 If a finite automaton M1 is a homomorphic image of a finite automaton M2, then E(M1) < E(M2). PROOF: Let g be a homomorphism of M2 onto M1 and then let h(m.,m.) (g(mi) g(m)). Also, let t be a tape that corrects i 3 = 1 J (m.,mj). We have 61(g(mi),t) = g(b2(m.,t)) since g is a homomorphism of M2 onto M1. Also, g(62(mi.t)) = g(62(mj,t)) since t corrects (mi.,m). Thus we have 1(g(mi),t) = g(b2(mb it)) = g(b2(m. t)) =- 1(g(m.),t)) Therefore t corrects (g(mi), g(mj)) = h(mim ). Thus h has the required property. QoEoDo Theorem 4.1 If A is a reduced finite automaton and B is any other automaton which realizes A, then E(B) > E(A), PROOF: If B realizes A, then B is a homomorphic image of a submachine of A (Hartmanis and Stearns, 1964). By using Lemmas 4.1 and 4.2 the theorem is proven. Q.E.D. 14

Corollary 4.1. If R is a regular set of tapes, a finite automata with minimum errors that recognizes R is the minimum auto.mata which recognizes R. Thus if we are interested in obtaining an automaton which realizes a given automaton (or recognizes a given regular set) and which has minimum:errors under our definition of the ordering, we should use the reduced automaton (or the minimum one associated with the set of tapes) since any state splitting, or adding states makes a new automaton whose errors are no less than those of the original one. The results of this section can be easily misinterpreted. It appears to claim that techniques such as triplicating and multiplexing are not effective since they increase the number of states. Hence, the errors in the multiplexed automaton are greater than those in the original one. However, the benefit of multiplexing and triplicating lies in that they reduce the probability of a malfunction causing an error between states which are not behaviorally equivalent. Since we consider automata without outputs the concept of behaviorally equivalent states does not arise. If we want to use our theory to handle such cases, we must consider the automaton modulo the relation of behavior equivalence. However, even after doing this, the multiplexed or triplicated automaton has errors which are not less than the original. Thus the advantages of these methods, like those of increasing the reliability of components in a physical 15

realization of the automaton, do not show up in the theory. On the other hand, a possible disadvantage does. 5. References Gilbert, E. and Moore, E. (1959), Variable-Length Binary Encodings, Bell System Technical Journal, 38, 933-967 ~ Hartmanis, J. (1962), Loop-free Structure of Sequential Machines, Information and Control, 5, 25-43~ Hartmanis, J. and Stearns, R. E. (1964), Pair Algebra and its Application to Automata, Information and Control, 6, 485-5070 von Neumann, J. (1956), Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components. In "Automata Studies," C. Shannon and J. McCarthy, editors, pages 43-98. Princeton University Press, Princeton, New Jersey. Winograd, S. (1964), Input-Error-Limiting Automata, Journal of the Association for Computing Machinery, 11, 338-351. 16

UNIVERSITY OF MICHIGAN 3 9015 02845 332511111111 3 9015 02845 3325