T H E U N I V E R S I T Y O F M I C II I C A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Technical Report THE APPLICATION OF ALGEBRAIC SYSTEMS TO FINITE AUTOMATA Yehoshafat. Give "o'n." ~,a.i ",, ORA Project 04995 under contract with: NATIONAL SCIENCE FOUNDATION GRANT NO. 22258 WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR June 1963

`-..,,: t -A W.:) 2 C ~

~1 INTRODUCTION In this paper we present a study of finite automata by means of the theory of finite monoids. In particular, we discuss constructions of direct products of finite automata. We do so in order to get Boolean combinations of finite automata and finite automata which define permutative events. In addition to these results, we reduce the basic decision procedures with regard to the behavior of finite automata to the study of the semi-ring extension of finite monoids. Essentially, most of our results appear in various forms in the literature. However, by the application of the theory of finite monoids we get a uniform treatment of finite automata which yields more economical practical procedures.

~2 REGULAR ALGEBRAIC SYSTEMS An algebraic structure of finite automata over the alrhabet V can be described as a homomorphism of V*, the free monoid generated by V, in the following way. Theorem 1 (Rabin-Scott): For any congruence relation p which is defined in V*, the set V*/p of equivalence classes of p in V* forms a monoid (which is finite iff p is of a finite index) with respect to the operation defined in V*/p by: p(x).p(y) = p(xy) Corollary 1.1: For any finite automaton A, or any regular event 1(4), one can construct a system <p, Mp, F> where: (i) NIp is a finite monoid, (ii) p is a homomorphism of V* into Mp, (iii) F is a subset of M; such that T(A) = p-l(F), -2

Thus, we can apply systems of the form defined in the corollary to Theorem 1, to describe finite automata and to generate regular events. We shall call such systems regular algebraic systems (or, in short, r.a. systems); <p, N > is said to be a structure of r.a. systems; and in particular, p <P, NI > is the structure of any r.a. system <p, NI P, F> for any FcM (which will be called the designated set of <p, Mp, F> ). The following theorem shows that regular algebraic systems form a special case of algebraic systems which generate regular events in the same way as r.a. systems do. The proof of Theorem 2 is straight forward and based on the application of right invariant relations to finite automata (Rahbin-Scott, 1959). Theorem 2: For any system of the form <f, G, F> where: (i) G is a finite groupoid (ii) f is a mapping of V* into G which satisfies f(xa) = f(x).f(a) for all xcV* and acV, (iii) F is a subset of G; the set f-l(F) is a regular event. -3

Remark: The condition stated in (ii) can be replaced by: f(ax) = f(a).f(x) for all acV and xcV*; but now obviously, the equivalence relation induced by f is left invariant. The relation between Rabin-Scott finite automata and regular algebraic systems is not one-one. An r.a. system <p, M, F> is said to generate the' event p-1'(F) and to simulate the Rabin-Scott finite automaton = <M, M e F> where M is the function from M xV to MP defined by Ml(m, a) = m.p(a) and e is the identity element of M, Not every finite autbmaton can be simulated by an r.a. system (though it can be simulated by a system as described in Theorem 2); but as one can prove, if 4 is a minimal Rabin-Scott finite automaton, then the minimal r.a. system (with respect to the order of the monoid of the system) which generates T(4) simulates 4. A compromise between the simulation of a given finite automaton and the generation of the event defined by the given finite automaton can be achieved by the following construction. Given the Rabin-Scott finite automaton A = <S, M, so, F>, the transitionmonoid associated with 4 is the monoid of functions: S-*S generated by -4

{fa: aV} where f (s) =f M(s, a). One can easily complete the transition monoid associated with 4- to be an r.a. system which generates T(A ) and represents 4 structurally (Buchi, 1960; Give'on, 1960). One can find a treatment of monoids associated with finite automata in this manner in (Myhill, 1960 & 1963).

~3 DIRECT PRODUCTS OF STRUCTURE, OF R.A. SYSTEMS AND THEIR APPLICATIONS TO FlIUITE AUTOMATA Our definition of direct products is a modification of the definition of direct product of finite automata (Rabin-Scott, 1959) in two aspects. We shall deal only with structures of finite automata via the structures of r.a. systems and leave the choice of the designated set free. This modification enables us to reduce various constructions of finite automata to the choice of a suitable designated set for a suitable direct product of structures. Furthermore, instead of using the direct product of the monoids under discussion, we take only a submonoid of it, which is in general a proper submonoid of the direct product. Thus, in general, we can save some unnecessary states. Given two structures <p, M > and <a, M > we define <p, M > x <o, Ma> =df <(P'o), M(P)> -6

where: (i) (p, a): V* + Mp 9 Ma is defined by (p, a)(x) = (p(x), a(x)), (ii) M(p, a) is the range of (p, a), i.e., it is the submonoid of Mp 9 M., the direct product of Mp and Mo, generated by (p, o)(V) = {(p(a), o(a)): acV ) For n structures <Pi, Mpi> we define their direct product by induction: n n-l iH <Pi, Mpi> df ( H <Pip Mpi>)X<Pn, MPn> i=l i=l Clearly, any direct product grouping of n structures <Pi, Mpi> is n isomorphic to H <Pi, Mpi> (the general associativity) and thus we can exi=l press it unambiguously by the form <(PI",.., Pn),M(p..' pn)> It is clear that the direct product of structures of r.a. systems is a structure of r.a. systems. Moreover, going back to Rabin-Scott's construction (Theorem 1), one can find that the congruence relation induced by the -7

homomorphism (pl,..., n) is the intersection of the congruence relations induced by *pl...Pne. This observation leads us to the first example of the application of direct products to finite automata; namely, to the construction of Boolean combinations of r.a. systems by means of direct products of structures of r.a. systems. For any Boolean set function BS(Xi,...,Xn), we denote by Bp(X1,..,Xn) the corresponding Boolean propositional function which is isomorphic to 8S(X,...,Xn). (For example, if Bs(X, X2, X3) = (Xl X 2) (X n X ), then 1 1 2 3 1 2 1 3 (X,1 X, X3) - (X1, X2) v ('X,, X). ) Given n regular algebraic systems i = <Pi, Mpi, Fi> and a Boolean set function 8S(XIP...*Xn) of n variables, we define: B(91,'",4n) =df <(P!,'",*Pn), M(pl,...pn)P B*(F 1...,Fn) > where: (i) <(P1,*..*), M(,...n) is the direct product of <Pi, MPi> (ii) B*(F,...,Fn) =df {(ml...*mn)cM(pl.. Pn) P -8

Theorem 3: For any Boolean set function Bs(X,...,Xn) of n variables 1 and any n regular algebraic systems Ai = <i, Mpi, Fi> we have T(S(4 l'.'n)) = (T( A ),...,T( n)) 1 1 (where T(4 ) is the event generated by 4 )..Proof: xeT(8{(4l,','n)) iff (Pi0... n)(x) E B*(F,...,Fn); i.e., iff Bp(P1(x)EF o...,pn(x)eFn). Hence xeT(B(4 f,...in)) iff xcBS(T( l))..., T( 4n)) Corollary 3.1: Given n ki-state finite automata, any Boolean combination of the events defined by them is defined by a finite automaton with no more n than n k. states. i=l 1 Our next application of the direct product of structures of r.a. systems yields a characterization of the regular permutative events. An event Ec V* is said to be permutative (or commutative in the terminology of Laing & Wright, 1962) iff for all xcE if y is a permutation of x then ycE. Let V = {a,...,an}; we shall denote by V(*) the regular event -9

a*ha*~... a* 1 2 " Theorem 4: Let Ec V* be a permutative event. E is regular iff E n V(*) is regular. Corollary 4.1: Es V* is a regular permutative event iff it is the permutation-closure of a regular sub-event of V(*). Proof: If E is regular then clearly EoV(*), being an intersection of two regular events, is a regular event. Assume that En V(*) is regular and generated by the r.a. system = <p, Mp, F>. For each Zlion we define the structure <Pi, Mpi> where: (i) Mpi is the submonoid of Mp generated by p(ai), hence, Mpi df {p(Y): yea.} (ii) Pi: V* * Mpi is defined recursively by -10

pi(X) = e (A is the empty word over V and e is the identity element of M1p ), 2. Pi(ai) = (ai), Pi(aj) = e for i f j, 3. pi(xy) = Pi(x) Pi(y) Now let A =df <(p p ) M(... F()> where 1 n <(1,...,OPn), M(O,...,P )> is the direct product of <Pi, Mpi> and 1 n F(*)=df {(ml...mn)~ M' m...m F. 1'"n (p,...,p ) 1 2 n 1 n Clearly, if xcV* and y is a permutation of x then (p,...pn )(x) = (p,o...,n)(y). Let xeV(*), say x = aklak2..a kn, ten n n 1 2 n p(x) = p (akl).p (ak2)...p (ann); hence if y is a permutation of xcEnV(*) then (p,...,p n)(y)cF(*). On the other hand, if ycV* such that (p1,...,Pn)(y)e(*) then y is a permutation of xcE rV(*). tence, since E is permutative, A'1 generates E and therefore E is regular. -11

~4 THE SEMI-RING EXTENSION OF MONOIDS AND ITS APPLICATIONS TO REGULAR ALGEBRAIC SYSTEMS A system <R, o, +> is said to be a semi-ring iff: (i) <R, o> is a monoid, (ii) <R, +> is a commutative monoid, (iii) o is distributive over + from both sides. A semi-ring <R, o, +> is said to be partially-ordered iff R is partially ordered by the relation < which is defined in R by A 4 B iffdf A + B = B. Obviously, a semi-ring <R, o, +> is partially-ordered iff <R, +> is an idempotent monoid. For any given monoid M, let MR be the monoid of the right translations of M which is isomorphic to M (under the correspondence x -+ fR where R R f M + M is defined by yfx=df yx; this is the monoid-theoretic generalizax tion of Cayley's Theorem). Let RM be the subalgebra of the binary relations in M with regard to complex-products and disjunctions which is generated by -12

MR and contains 0 (the empty binary relation in M). Clearly, the set of relations of RM is the minimal set of binary relations in M which is closed under disjunction and includes MR and contains 0. It is achieved by taking all the finite disjunctions of the relations in MR including the empty disjunction which yields 0. Furthermore, RM is a partiallyordered semi-ring which is finite iff M is finite. A different method of embedding M in a partially-ordered semi-ring which is isomorphic to RM is as follows. Let <PfM, o, +> be the algebra defined by: (i) PfM is the set of all finite subsets of M, (ii) o is the operation of complex-product of subsets, i.e., AoB = {ab: acA & beB}, (iii) + is the operation of set-union, i.e., A+B = AuB. -13

Theorem 5: For any monoid M, <PfM, o, +> is isomorphic to RM under the correspondence fR defined by fR(A) =df V{fR: a A} Proof: Since any relation in RM is a finite disjunction of the relations in MR we get that fR is a mapping of PfM onto Ri. It is immediate that: fK (A+B) = fR(A) v f (B) and fR(AoB) = fR(A) * fR(B), hence fR is a homomorphism of <PfM, o, +> onto RM. R Now, let A be any finite subset of M then (e,a)fR (A) iff acA, therefore A = {a: (e, a)cfR(A)}. Hence, if fR(A) = fR(B) we get {a: (e, a)cfi(A)} = {b: (e, b)cfR(B)} and therefore A = B. Going back to finite monoids we have that RM is isomorphic to the algebra of the subsets of M with regard to complex-products and unions of sets. Hence, we are allowed to use the simple notation of the algebra of the subsets of M in referring to RM also. The proof of the following theorem -14

can be derived from the properties of nxn binary relations (as a special case of nxn lattice matrices, Give'on, 1963) or can be constructed independently. Theorem 6: Let M be a finite monoid of order n. For any AcRM1 we define A* =df (I+A)n-1 where I = {e}; and get: 00 (i) for all k>O: Ak,<A* and thus A* = VAk; k=o (ii) for all kO: Ak- (An- A*) = An- A*. The importance of RM to the study of finite automata, and in particular the importance of Theorem 6, is derived from the introduction of the analogue of the transition matrix associated with a finite automaton (Give'on, 1960) which was suggested first by Burks & Wang (as the characteristic matrix in Burks & Wang, 1957). We associate with a given structure <p, Mp>, of regular algebraic systems over the alphabet V, the element Tp of RM which is defined by Tp =df p(V) = {p(a): aeV} Clearly, Tk = {p(x): xV k} = p(Vk) -15

and T* = {p(X): XEV*} = p(V*) Thus, Theorem 6 implies directly: Corollary 6.1 Let A = <p, Mo, F> be a regular algebraic system over the alphabet V, where Mp is a finite monoid of order n. k Then: (i) A- generates a word of length k iff T nF E 0 (ii) 4 generates a non-empty event iff Tn F ~ 0 (iii) A generates an infinite event iff (Tn o T) r F ~ P. In fact, by introducing Tp, we associate with =2 <p, Mp, F>, which is an r.a. system over V, another r.a. system 1 = <T t F> over a single-letter alphabet {t}, where: (i) t* is the submonoid of RM generated by Tp, (ii) T is the homomorphism of {t}*, the free monoid generated by t, onto t* induced by T(t) = T P p The relation between J1 and A is given in statement (i) of Corollary 6.1, i.e.: IA-1 generates a word of length k iff A- generates a -16

word of length k. As an immediate result of this construction, we get the following well known property of regular events: Corollary 6.2: Let E be any regular event and let IEl be the set of non-negative integers defined by: kciEj iffdf E contains a word of length k. Then IEJ = S u S where: 1 2 (i) S is a finite set, (ii) S is a finite union of ultimately periodic sets with the same period. Clearly, Corollary 6.1 provides us with effective procedures for the following basic decision problems concerning finite automata: To decide whether a given regular algebraic system (or a given finite automaton) - (i) generates a word of a given length; -17

(ii) generates a non-empty event; (iii) generates an infinite event. These three decision procedures are almost independent of the number of letters in V (only the construction of Tp is dependent on it). By the association of! |i they are, in fact, reduced to Rabin-Scott's procedures as applied to a single letter automaton. The fact that IA1 represents (in the manner discussed at the end of ~2,) an n-state non-deterministic automaton, which is in general equivalent to a 2n-state deterministic automaton; or the fact that there is no guarantee that t* is of order n do not invalidate Corollary 6.1 as it stands. Moreover, if we replace in Theorem 6 and in Corollary 6.1 the expression "M is a finite monoid of order n" by "Mp is isomorphic to a monoid of nxn binary relations" (or even "of nxn lattice matrices", Give'on 1963) then both Theorem 6 and Corollary 6.1 are applicable even to n-state non-deterministic automata since these automata are representable by r.a. systems with monoids of nxn binary relations. -18

We can shorten the computations involved in the decision procedures implied by Corollary 6.1. Observe that for any AcRM, where M is of order n (or where M is isomorphic to a monoid of nxn binary relations) we have: A* = A([lg2(n)]+l) where A(k) is defined recursively by: A(1) = I+A, A(k+l) = (A(k))2. Note also that in the case where M is isomorphic to a monoid of nxn binary relations (or of nxn lattice matrices) RM can be taken as the minimal subsemi-ring of nxn binary relations (lattice matrices) which includes M, which is a homomorphic image of.the original RM. -19

BIBLIOGRAPHY [1] J. R. Buchi, "Mathematical Theory of Automata: Notes for a seminar," given by J. B. Wright and J. R. Buchi, Fall 1960, The University of Michigan [2] A. W. Burks & H. Wang, "The Logic of Automata," J. ACM, Vol. 4, No, 2-3, April-July 1957. [3] Y. Give'on, "Boolean Matrices and Their Application to Finite Automata," Technical Report No. 5, Applied Logic Branch, The Hebrew University of Jerusalem, September 1960. [4] - - - "Lattice Matrices," [5] R. Laing & J. B. Wright, "Commutative Machines," Technical Note, The University of Michigan (ORA), December 1962. [6] J. Myhill, "Transformation Groups Associated with Finite Automata," Programming Concepts, Automata and Adaptive Systems, College of Engineering, The University of Michigan, 1960 Summer Session. -20

[7] - - - - "Finite Automata, Semigroups and Simmulation," Automata Theory, College of Engineering, The University of Michigan, 1963 Summer Session. -21

UNIVERSITY OF MICHIGAN 3 9015 02825 9904