W W. l 1 101 STRUCTU RE (3'? ALF‘E‘QMATA Thasés 9m rho £39ng of Ph. D.- iviéfiélfiski‘é S‘fiiffi {WEVEREITY fimca fimhaf? Earms This is to certify that the thesis entitled STRUCTURE OF AUTOMATA presented by Bruce Herbert Barnes has been accepted towards fulfillment of the requirements for _Rh_._D_-__degree mMathematics C17 - T7 # , ’ t.‘C-\(ZL(:(7 if 21, -w" Lyz) ,_, Major professor Date November 22, 1960 LIBRARY Michigan State University STRUCTURE OF AUTOMATA BY BRUCE HERBERT BARNES AN ABSTRACT Submitted to the School for Advanced Graduate Studies of Michigan State University of Agriculture and Applied Science in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY 1960 Approved ,jy%%{‘g‘7 fl 2.4x’“_/ccc?/f,/ ABSTRACT This dissertation deals with the structure of finite automata and sequential machines. The first chapter is an extension of Rabin and Scott's work on finite automata. The sets of tapes acceptable to a finite automaton are characterized through the use of equivalence classes. This is done for four types of finite automata. These are: (1) One initial state and not all states final. (2) More than nne initial state and not all states final. (3) One initial state and all states final. (4) All states both initial and final. In the second chapter sets of input-outputsequences that are acceptable to a sequentialmachine are characterized through the use of equivalence classes similar to those employed for finite auto- mata. It is shown how the set of input-output sequences acceptable to a sequential machine can be obtained from the characterization of the set of tapes acceptable to a particular state of the sequential machine. This characterization is used to prove some theorems concerning the reduction of sequential machines to minimal state form. In Chapter III the structure of finite automata and sequential machines is studied through the use of connection matrices. The properties of a positive connection matrix which distinguishes it from a strongly connected matrix are discussed. It is shown that all the powers of a positive connection matrix are strongly connec- ted, but the same statement for strongly connected matrices is -2- not true. This condition is reduced to just the first n powers of an n x n connection matrix need be strongly connected to insure that a connection matrix is positive. It is also pointed out that the theorems of Chapter III apply to prim- itive matrices of non-negative real numbers. STRUCTURE OF AUTOMATA BY BRUCE HERBERT BARNES A THESIS Submitted to the School for Advanced Graduate Studies of Michigan State University of Agriculture and Applied Science in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOHHY 1960 Approved 0452,34 G) 24/ $212!)» -11, ACKNOWLEDGMENT The author wishes to express his gratitude to Professor Gerard P. Weeg, for his guidance and encouragement throughout the writing of this paper and during most of his graduate study. -iii- TABLE OF CONTENTS INTRODUCTION . . -.‘ . . . . . . . l EINITE AUTOMATA . . . . . . . . . 4 SEQUENTIAL MACHINES . . . . . . . . 22 INDECOMPOSABLE MATRICES AND THE STRUCTURE OF AUTOMATA . . . . . . . . . . 40 BIBLIOGRAPHY . . . . . . . . . . 5 0 INTRODUCTI ON The investigation into the theory of sequential machines have had a very recent origin. It was in 1955 and 1956 that Mealy [ 22] , Moore [23] and Huffman [ 17] , published what are evidently the pioneering papers in the field. These authors, and most later ones, consider a sequential machine to be a device capable of assuming any one of a finite set of internal states, such that when an input symbol is presented to the machine, an output symbol is produced by the machine and the sequential machine assumes another state. There are three major areas in the study of sequential machines. These are: (l) The construction of electronic devices, which have proper- ties similar to those mentioned above. Such devices are commonly called sequential transducers. Considerable work has been done in the area in recent years, especially since the advent of high speed digital computers and other types of process control apparatus where the process is sequential in nature. Huffman [ l7] , Cadden [6] , Unger [26] and others have done a considerable amount of work in this field. (2) The synthesis and analysis of state diagrams (these are weighted graphs used to represent sequential machine) which are used to facilitate the construction of sequential machines. This area has been dealt with by Huffman [ l7] , Mealy [22] , Hohn [ 3], Aufen- kamp [1, 3, 4], Ginsburg [10, ll, 12, 13], Bellman [5] , Gillespie [l] and others. -2- (3) The study of sequential machines as a mathematical system. Kleene [l9] , Moore [23], Nerode [24], Rabin and Scott [25], Ginsburg [9], Weeg [ 18, 27] and several others have worked in this field. This last area of sequential machines is the subject of this disser- tation. Three separate but related topics will be covered in this disser- tation. They are finite automata, sequential machines and connection matrices. A finite automaton is a sequential machine without outputs. The set of sequences (called tapes) which are suitable for a finite automaton are characterized through the use of equivalence classes. Four types of finite automata are discussed in Chapter I. The major result of the first chapter is that a set of tapes, U, is the acceptable set of tapes for a finite automaton, in which each state is an initial state and also each state is a final state, if and only if U is complete (that is, if x is any tape in U, then any portion of x is in U) and is the union of all but One of the equivalence classes of a parti- cular right invariant equivalence relation of finite index. In Chapter II, the set of sequences of input-output symbols (called I-O sequences) which are suitable for a sequential machine are characterized by the use of equivalence classfle. These equivalence classes are used to prove some theorems concerning special classes of sequential machines. The main theorem of this chapter is similar to that of Chapter 1, except, due to the outputs, the conditions are more stringent. -3- For the purpose of study of the structure of sequential machines a connection matrix is often used. A special class of these is the class of strongly connected connection matrices. A subclass of the class of strongly connected sequential machines is that of positive machines. The properties which distinguish this subclass from the class of strongly connected connection matrices are discussed in Chapter III. The major distinction is that a positive connection matrix has all of its powers strongly connected. It is shown that this requirement can be reduced to the point that just the first n powers of an n x n connec- tion matrix need be strongly connected to insure positiveness. Chapter I FINITE AUTOMATA An automaton may be thought of as a black box which will accept tapes (questions). As the tape proceeds through the box the internal mechanisms of the box assume different configurations and when the tape is completely accepted by the black box an answer is given (yes or no). This answer depends on the configuration of the internal mechanism of the black box. The method of giving the answer might be by means of a light, which is: on when the configuration of the inter- nal mechanism corresponds to an answer of yes. A tape (question) is called acceptable to a finite automaton if the answer corresponding to this question is yes. Several interesting questions arise concerning acceptable sets of tapes. Among these are: (1) What are the properties of a set of acceptable tapes ? (2) For every set of tapes U is there an automaton having U as its set of acceptable tapes? (3) Given a set of tapes, is there an effective procedure to ascertain if there exists an automaton accepting this set of tapes, and if so, can this automaton be produced? These are the problems that are discussed in this chapter. Before these ideas are formalized, however, a few definitions will be needed. These definitions will largely be similar to those found in the literature. -4- -5- Definition 1. A tape x is a finite sequence of elements from a non-empty finite set 7‘... The elements of E are called tape symbols and Z is called the alphabet. The null tape (i. e. , the tape with no symbols) is denoted by X. Definition 2. The set of all finite tapes over the alphabet Z‘. is denoted by T. A tape x is written in the form x = 0'00’1 . . . on where oi are elements of 2. If x = 0'0 . . . (Tn-l and y = 0.0 . . . urn-1 then by xy 18 meant the tape xy 2 0'0 . . . Un-laO . . Qm-l' A portion of tape x is denoted by ixj' which means that portion of the tape x beginning with the ith position and continuing up to and including the j-l posi- tion. By ixi is meant the null tape. Definition 3, [25, p. 116] . A finite automaton of type 1, also called an automaton when no confusion will result, over the alphabet 23 is a system A* = (S, M, 80, E) where S is a finite non-empty set (called the set of internal states of A), M is a function defined on the Cartesian product S x Z of all ordered pairs of states and input symbols with values in S (called the table of transitions or moves of A*), 30 is an ele- ment of S (called the initial state of A*) and F is a non-empty subset of S (the set of designated final states of A*). There are several methods for specifying a finite automaton. One common method is to give a table, called the table of moves, and a list of final states. -6— Example: Let A* = (S, M, so, F) be defined over the alphabet 2‘. = { a, b, c} in the following way: S = {$0, 81’ 52} , with S0 the initial state. F = {$2} the set containing only 52‘ M is defined by Table 1, with the following interpretation. If 81 is the present state, oi the present input and 8n the next state, then M(s., 0'.) = s . 1 j n Table 1 Present State Next State Present Input a b c so 81 s2 s2 S1 S2 81 so 52 so 81 s2 For the purposes of analysis of an automaton... a pictorial display is often useful. This is usually given in the form of a state diagram which parallels Moore's transition diagram of a sequential machine. A state dia- gram is a weighted directed graph with each vertex corresponding to a state of the automaton. The states are usually drawn as circles with an ordered pair (a, b) inside the circle, where a is the number of the state and b is 1, if this state is final, and 0, if this state is not a final state. If M(sk, 0‘1) = se, then there is a directed line segment from vertex k to vertex e labelled oi. Figure 1 is the state diagram for the previous example . Figure 1 In the remainder of this chapter the given definition of an automaton will be modified and its properties compared with those given by Rabin and Scott [25] . In the Rabin and Scottltype automaton M(si, a'j) is defined for all combinations of si in S and a'j in Z. This property will now be weakened by requiring that transitions be defined only for some state -input combinations, but not necessarily for all state -input combinations . -8- Definition 4. A finite automaton of type 2 over the alphabet E is a system A = (S, M, s F) where S is a finite non-empty set (called the 0. internal states of A), M is a function defined on a subset L of the Cartesian product S x Z of all pairs of states and input symbols into the set of internal states S, 30 is an element of S (called the initial state) and F is a non-empty subset of S (called the set of final states of S). Henceforth, the symbol A* will be used for a Rabin and Scott type automaton and A for a machine as defined according to Definition 4. It is necessary for many of the proofs to extend the definition of M from L, a subset of S x Z, to H, a subset of S x T. This is accomplished in a manner similar to that of Rabin and Scott [125] : M(si. X) = 81 M(si, xoj) = M(M(si, x), oj) for si in S, x in T, and O'j in E. If M(si, x) is not defined or M(M(si, x), oj) is not defined, then M(Si’ xcrj) is not defined. Definition 5. A tape x is called an acceptable tape for an automaton A = (S, M, so, F) of type 2 if M(so, x) is contained in F. The set of all tapes which are acceptable to an automaton A of type 2 is denoted by T(A), and is called the set of acceptable tapes for the automaton A. Definition 6. The setj is the set of sets of tapes over the alphabet 2: such that U is in 7 , if and only if U = T(A) for some automaton A over 2'3, of type 2. -9- Theorem 1. If U is a set of tapes such that U .= T(A)],for some automaton A of type 2, then there exists an automaton A* of type 1 such that U = T(A*) and conversely. Proof: If U = T(A), then the automaton A* is constructable from the automaton A. This is done in the following manner: Let 5* = SU{s '} where S is the set of states for the automaton A and {8'} is the set consistin of 3' alone where s' is distinct from an state in S. Define: g Y M*(si, Uj) = M(Si’ crj) if M(si, Uj) is defined. M*(si, Gj) = 8‘ if M(si, O'i) is not defined and M*(s', (Ti) = s' for all “1 contained in Z. s* -= 80 and F* = F. For any tape x in T(A), x is also in T(A*), because M*(so, x) = M(so, x) and if M(so, x) is in F, M*(so, x) is in F. Likewise, if any tape y is not in T(A), then it is also not in T(A*), for if M(so, y) is defined, M*(so, y) = M(so, y) which is not in F and thus not in F*; while if M(so, y) is not defined then M*(so, y) = s' which is not in F*. One can also observe that an automaton A* of type 1 is also an automaton A of type 2. We have,therefore, shown that U = T(A) if and only if U = T(A*) for some A and A* of type 2 and 1 respectively. The important difference between the two kinds of automata is that an automaton A probably would not require as many transitions and possibly even fewer states than the automaton A*. This can be seen from the following example. Let U = {10101} . The automaton A of type-2 of figure 2 has U as its set of acceptable tapes. -10.. 0W o 0 o so Figure 2 The Rabin and Scott type automaton A* of figure 3 also has U as its set of acceptable tapes. As can be seen the automaton A has one less state than the automaton A* and 9 less transitions. Figure 3 -11- Not every set U of tapes is a set of acceptable tapes for some auto- maton. This has been shown by Rabin and Scott [25] . Their proof, how- ever, produced a set of tapes not acceptable to any automaton A*, while the proof of Theorem 2 is an existence proof. Lemma 1. The cardinal number of the set 7 is K0. Proof: Let c denote the cardinality of Z. If A = (S, M, s F) has 0. n states, then for each state Si’ M(Si’ Uj) can be any one of n states or not be defined. Thus, there are (n+1)C possible ways to define the function M for each state and for any fixed n there are at most [(n+l)c] n possible ways to define the function M. Since the number of non-empty subsets F n of S is 2n-1, and s can be any one of n states, there are n(2n-l)[ (n+1)c] 0 possible machines with exactly n states. A countable number of sets, each of which contains all possible finite automata with a given number of states, can be formed. Hence, there are at most Mo finite automata and at most Rose” of acceptable sets of tapes over the alphabet 2- Let S be a set of n states. Let s1 be the initial state and F the set containing only the state an. Let M(si, oj) = si+1 for 1é-ién and let “i be undefined for all i except 1, then this automaton accepts the tape 0'10'1 . . . 0-1 and only this n tape. In this way R distinct sets of acceptable tapes are produced. This 0 shows that the cardinality of ] iséfli . 0 Theorem 2. There exist sets U of tapes, such that U is not the set of acceptable tapes for any automaton A, of type 2. Proof: Since the cardinality of T isxthere are 2%" = 0 sets 0 of sets of tapes over the alphabet 21 Thus making use of Lemma 1, there exist sets of tapes which are not acceptable to any finite automaton. -12- Rabin and Scott [25] give several theorems concerning acceptable sets of tape, which are due to Myhill, Nerode, and themselves. We will now generalize these theorems. Many of these theorems make strong use of equivalence relations among the tapes of T. Definition 7. An equivalence relation R over the set T of tapes is right invariant, if whenever ny, then szyz for all z in T. There is also an analogous definition for a left invariant equivalence relation. Definition 8. An equivalence relation over the set T is a congruence relation if it is both left and right invariant. Definition 9. An equivalence relation over T is of finite index if there are only finitely many equivalence classes under the relation. With these definitions available it is now possible to state the following theorem, which is due to Myhill [25, p. 117] , and prove its applicability to an automaton A of type 2. Theorem 3. Let U be a set of tapes over the alphabet Z. The following three conditions are equivalent. (1) U is in T (2) U is the union of some of the equivalence classes of a congru— ence relation over T of finite index. (3) The explicit congruence relation 5 defined by the condition that for all x, y in T, x E y if and only if for all z, w in T, whenever -13- zxw is in U, then zyw is in U, and conversely, is a congruence relation of finite index. Proof: As pointed out in Theorem 1, for every automaton A of type 2, there is an automaton A* of type 1 which has the same set of acceptable tapes. Thus, if T(A) is in 7/, so is T(A*) and both sets have the same preperties. The-following theorem, which is a generalization of a theorem due to Nerode [24, p. 543] , applies to automata A* of type 1, hence, to auto- mata A of type 2. Theorem 4. Let U be a set of tapes. The following three condi- tions are equivalent: (1) U is in 7/. (2) U is the union of some of the equivalence classes of a right invariant equivalence relation over T of finite index. (3) The explicit right invariant equivalence relation E defined by the condition that for all x, y in T, xEy if and only if for all z in T, whenever xz is in U, then yz is in U and conversely, is an equivalence relation of finite index. Corollary 1. Let U be in 7/. If the number of equivalence classes of T under the relation E is n, then the least number of states in any automaton having U as its set of acceptable tapes is n-p, where p is 1 if there exists an equivalence class [y], such that for any x in [y], xz is not in U for all z in T; otherwise p is 0. Proof: Let each equivalence class denote a state. Let s0 = [7k] (the equivalence class containing the null tape). Let F be the -14- set of equivalence classes which contain a tape from U. Define M as follows: M“ x], 02].):[xo-j1‘ Since M([Px] , x) = M(so, x) = [x], this automaton has U as its acceptable set of tapes. If one of the equivalence classes does not contain a tape y such that yz is in U, for some tape 2 in T, it is not necessary to have a state corresponding to this equivalence class in this automaton. Thus, this state and all the transitions emanating from it and terminating in it can be removed. This can be seen from the following argument. If xEy then M(so, x) 7! M(so, y) for any automaton A of typerZ. We have therefore, that for each equivalence class, which contains some tape x such that M(so, x) is defined, a distinct internal state in the machine. If we define M([x] , 0') = [xcr] where [x] and [x0] are equivalence classes con- taining a tape y such that M(s y) is defined, we produce an automaton which 0, accepts the set of tapes U, and which has exactly as many states as there are equivalence classes under E which contain a tape for which M(so, x) is defined. The above corollary is a generalization of Nerode's theorem [25, p. 118] . However, it is interesting to notethat with the gener- alized definition Of an automaton there may be one less state needed to produce an automaton which will accept the set of tapes U. The next three theorems by Rabin and Scott depend only on the equivalence relation and are, therefore, also true for the automata A of type 2. -15- Theorem 5. If x is in T, then {x} , the set consisting of x alone .. n7.” Definition 10. If x is the tape 0' . on, then x* is the tape 102. (r If U is a set of tapes then U* is the set of tapes such nO‘n-l . . . 0'20'1. that x is in U if and only if x* is in U*. Theorem 6. If U is in 7/, then U* is in 7 Theorem 7. The class } is a Boolean algebra of sets. In the remainder of the chapter we will generalize the idea of an automaton and acceptability of tapes. Through an evolution of automata we will arrive at an automaton in Which all states are initial states and all states are final states, with a tape being acceptable if it "reads" through the ”reader". This corresponds to the more generally accepted idea of an automaton and also forms a good foundation for the next chap- ter on sequential machine. Definition 11. An automaton B of type 3 over the alphabet Z is a system B = (S, M, O. F) in which M, S and F are defined as for an auto- maton A and Q, the set of initial states, is a non-empty subset of S. Definition 12. A tape x is acceptable to an automaton B of type 3 if M(si, x) is inF for some 5.1 in Q. The set of all acceptable tapes to an automaton B of type 3 is denoted by T(B) and is called the set of acceptable tapes for B. -16- Theorem 8. Let U be a set of tapes.U = T(B) for some B of type 3 if and only if U = T(A) for a suitable automaton A of type 2. Proof: Let S' be the set of all subsets of S, s ' the set Q, and let 0 F' be the set of all subsets of S which contain at least one state in F. Define M' in the following manner: If si' = {$01, . . . , so} then n n M'(si'. o-j) = U {M(sm, Uj’} . The definition of M' is extended a: 1 to S' x T the same way in which the definition of M was extended. Let A = (S', M', 80', F'). It can now be shown that the automaton A accepts the same set of tapes as the automaton B. This is accomplished in the following manner. Assume x is an acceptable tape for the automaton B. Then for some state 81 in Q, M(Si’ x) = sj, which is in F. Let x = 0001 . . - O'n_1. Consider M'(Q, x) = so". Since M(si, x) = SJ. is a state in F and sj is in s ', s ' is a state in F'. a. 0. Assume now that x is acceptable to the automaton A. Then M'(Q, x) = sn' is in F'. Since sn' is in F', sn' contains some state sn in S such that sn is in F. There is some state, say sj, such that sj is in Q and M(sj, x) = Sn' This can be seen by tracing the states of A back from sn'. Let so', . . ., sn' be the sequence of states ofA which A assumes as A accepts the tape x. There much be some state s in s ‘ such that n-1- n-1 M(s , o- ) = s , otherwise 5 would not be in s '. Likewise, there is n-l n n n n . . . , some state Sn-Z such that Sn-Z is contained in sn_2 and M(sn_2, (rm-2) = s . In general there will be a state s . in s .' such that M(s ., (T .) n-1 n-3 n-3 n-3 n-3 = sn-j+l' Thus, we see that there is a sequence of states beginning with a state Q and ending in sn'. Since an is in F, x is acceptable to the automaton B. -17- If the set Q = {so} , a set containing only one state, then the auto- maton B of type 3 is essentially equivalent to an automaton A of type 2. Hence, a set of tapes is acceptable to an automaton B of type 3 if and only if it is the acceptable set of tapes to an automaton A of type 2. Even though the definition of an automaton and, hence, the accep- tability of tapes for an automaton has been changed, we have not changed the type of sets which are acceptable to an automaton. We will in many cases, however, be able to use a smaller number of states to produce the automaton accepting the set of tapes. If it is the case that Q = S, that is, all states. are initial, the set T(B) for an automaton B of type 3 has the further property of terminal completeness. This means that if a tape x of length n is in T(B), :the'rmlxn is in T(B) for all 0 5i i n. This property of T(B) can be easily seen from the fact that if M(so, x) is in F, then M(M(so, 0xi), ixn) is in .F. Since M(so, 0xi) is in Q, ixn is in T(B). In some cases it might not be possible to ascertain whether or not the automaton stopped in a final state, although it would be possible to determine if a tape has been "read" in its entirety. This concept of acceptability corresponds to all statesrof an automaton being final. The definition of..an;a:1rtmtiaton will now be changed to correspond to this new concept of acceptability. Definition 13. An automaton C of type 4 is a systemC = (S, M, so), where S is the set of internal states and M is a mapping of a pr0per subset L of S x 2 into S and s0 is an element of S, called the initial state. A tape x is acceptable if M(so, x) is defined. (If L were not a prOper subset of S x 22, then the automaton C would accept all tapes). -18- Definition 14. A set of tapes U is initially complete if it contains X = all its initial segments, that is if x = 0001 - - - O'n_1 is in U than h o oool. . . “h-i is inUtoroshén. Theorem 9. A set U of tapes, denoted by T(C), in T is the accep- table set of tapes for an automaton C of type 4 if and-only if U is initially complete and U is the union of all but one of the equivalence classes of a right invariant equivalence relation E over T of finite index, unless U = T in which case U is composed of one equivalence class. Proof: Let T(C) be the acceptable set of tapes for some automaton Coftype4. Ifx=0' . 0' 0' . is in T(C) then M(s , x) is defined. This 0 1 n-l 0 case occurs, however, if and only if M(so, x) is defined for all x. in T(C). 0 1 Thus, T(C) is initially complete. That T(C) is the union of all but one of the equivalence classes of a right invariant equivalence relation over T of finite index is a trivial consequence of the fact that C is an automaton of type 2 with F = S and all classes except the one containing the tapes x such that M(so, x) is not defined are contained in T(C). Let U be an initially complete set of tapes which is the union of all but one of the equivalence classes of a right invariant equivalence relation over T of finite index. Since U is the union of some of the equivalence classes of a right invariant equivalence relation over T of finite index, we can construct an automaton A of type 2 which has U as its set of acceptable tapes. If we choose some tape y not in U and remove M(so, y) fromA along with all transitions to and from this state we will again have an automaton. This new automaton has U as its set of acceptable tapes and is of the type 4. -19- Since the state which-was removed was not final and all but one of the states of the automaton were final, all of the states of the new automaton are final. Since U is complete, no state which is necessary for M(so, x) to be defined for any x contained in U was removed, thus the new automaton C is of the type 4 and accepts the set U. An automaton will now be defined in the form most useful to the notion of a sequential machine, the subject of the next chapter. The notion of acceptability is now, "Is there some state such that if the automaton is in this state and a tape 2 is presented to it, will the automaton read the entire tape? " Definition 15. An automaton D of type 5 over the alphabet Z is a system D = (S, M) where S is a non-empty set (called the set of internal states) and a mapping M of a non-empty subset L of S x E into S. Definition 16. A tape x = 0' cl . . . O'n_1 is acceptable to the auto- 0 maton D of type 5 if there exists some 5.1 in S such that M(Si’ x) is defined. The set T(D) is the set of all those tapes and only those tapes acceptable to D. Theorem 10. For every automaton D cff type 5 there is an automaton C of type 4 such that T(D) = T(C). Proof: Since the automaton D of type 5 is also of type 3, according to Theorem 3, an automaton A of type 2 can be found which accepts T(D). Since each state of the automaton D is final, T(D) is initially complete and the union of all but one of the equivalence classes of a right invariant equivalence relation over T of finite index. This then gives us that -20- the automaton A is also of type 4, and we have an automaton C of type 4 which accepts T(D). Since the automaton D has each of its states as initial states the set T(D) is terminally complete. Likewise, since each of its states is final, the set T(D) is initially complete. This leads to the interesting property of an automaton of the type 5, that of total completeness. Definition 17. A set of tapes U is totally complete, if whenever a tape x of length n is in U then. ixj is in U for Oéi éj -_ 4n. That is, if the tape x is in U then any contiguous portion of it is in U. Theorem 11. A set of tapes U is totally complete if and only if it is both initially and terminally complete. Proof: If the set of tapes U is totally complete then by definition it is both initially and terminally complete. Assume the set of tapes U is both initially and terminally complete. We wish to show that if x is in U then ixj is in U, for 051 {‘j4 - n. Since x. is in U. If we now apply the condition of ter- U is initially complete 0 J minal completeness to x. we have that ixj is in U. It has, therefore, 0 J been shown that the set of tapes acceptable to an automaton of type D is not only initially and terminally complete but is also totally complete. We have now arrived at one of the goals of this chapter, that is, we have characterized the set of tapes acceptable to an automaton D of type 5 which is similar to a sequential machine except that no outputs have been associated with this automaton. In the next chapter we will consider -21- sequential machines, which have outputs associated with them, and point out in which ways these theorems will have to be changed to be applicable to sequential machines. Chapter II SEQUENTIAL MACHINES The idea of sequential machines has come into use in recent years in many fields of study. It has been employed by McCulloch and Pitts [20] and others in the representation of nerve nets. Kleene [ 19] used this idea for his work on the representation of events. Huffman [11]], Mealy [22] , Hohn [2] , Aufenkamp [2, 3], and Ginsburg [ 10, 11, 12, 13] have dealt extensively with the synthesis and analysis of sequential machines to be used in the design and construction of computers and other types of prodess control equipment, where the process is essentially sequential in nature. In this chapter we will characterize the sets of input-output sequences which are acceptable to a sequential machine. A sequential machine can be thought of as a set of states (possibly internal configurations of a device) "accepting" input sequences and “producing" output sequences, such that if the device is in a state and is given an input, the internal configuration changes to a new state (possibly the same state again) and an output is given. There are two commonly used models of sequential machines. One, the Moore [23] model, associates outputs with states. The other associates outputs with transitions of one state to another with a given input. Sequen- tial machines of this type are known as the Mealy [22] model, and are the type that will be primarily discussed in this chapter. A Mealy model sequen- tial machine is disfined formally in the following way. -22- -23- Definition 1. A sequential machine with input alphabet Z: and output alphabet O is a system A = (S, P) where S is a non-empty finite set (the internal states of A), and P is a function defined as a non-empty (not necessarily proper) subset J of the Cartesian product S x 0. Specifically if si is in S and 0'j is in Z, P(si, O'j) =(M(si, O‘j), N(si, O'j)) where M is defined as in Chapter I and N is a function of the subset L of S x Zinto 0. An input-output sequence x is a finite sequence of ordered pairs (0'1, Oj) where O‘iIis an input symbol and Oj is an output symbol. x will be written as :1- where xI is the input sequence and x0 is the output sequence. In order to discuss the idea of input-output sequences, it is neces- sary to extend the definition of P. Let 6 be the set of all finite sequences of input symbols, and k the null sequence of 6. Let Q be the set of all finite sequences of output symbols with p- the null sequence of output symbols. The function P is extended from S x E to S x 9 by extending the definitions of the two functions M and N. M is extended just as in Chapter I, while N is extended to S x 9 in the following way: N(sj. X) = it N(sj, 0'00'1 . . . (Tn-l) .-.- N(sj, 0'0) N(M(sj, 0‘0 ), crl . . . (Tn-1), where sj is any state in S and cool . . . (Tn-1 is any tape in): such that M(sj, 0'0) is defined. The function P is extended from S x 2 to S x 6 by P(si, x1) = (M(si, x1), N(si, xI)), -24- where xI is an input sequence. There are several methods for specifying a sequential machine. Some of these are as follows: (1) Transition and output tables. This is a table, called a next state- output matrix by Ginsburg [12], which has a list of states in a vertical col- umn and a list of inputs in a horizontal row. In the position corresponding to the state 31 and the input O'j is the ordered pair (sp, oq) corresponding to the next state and the output which occur when the machine is in the state si and input O'j is given, that is P(Si’ 03) 2 (sp, Oq). For example, let 2 and 0 be the sets 2‘. = {a, b} and O = (a, B} . Then let A be the sequential machine with s = { o, 1, 2, 3, 4, 5} and with P defined by Table 1 with the interpretation, that if the statue is Si and the input crj, then the next state and output pair is P(s.1, oj). Table l State Next State and Output Next State and Output Input a Input b 0 (0, c1) (1, 0.) 1 (O, o.) (2, a) 2 (0. a) (3, B) 3 (4. s) (3. p) 4 (5, s) (3. [3) 5 (0, c1) (3, (3) -25- (2) A pictorial method for displaying a sequential machine is the state diagram. This is a directed graph in which the vertices represent the states and the directed line segments represent transitions. If P(si, Up) = (sj, oq), then the directed line segment from state si to state Sj is assigned the ordered pair (op, oq). The state diagram for the previous example is: (a, a. . (b, <1) 0 1 (b. a) a i} (a, 0.) (b: {3 Figure 1 ((3) A useful tool for the analysis of sequential machines is the connection matrix [2] . If P(si, Up) = (sj, oq) then the i, j th position is the ordered pair (op, Oq) or the formal sum of such pairs. If there is no input crp such that M(si, up) = sj then the i, j th position is zero. -26- The connection matrix for the previous example is: (a, o) H» a) o o 0 o (a. a) 0 (b, o) (1 o o (a, o) o o (b, s) o o o o o (b. 5) kn o) 0 o o o (b, s) o (a, p) (a, o) o o (b, s) o o ,/ Figure 2 The work done by Rabin and Scott [25] , together with the results of Chapter I, when considered in the light of sequential machine theory, leads us to the investigation of acceptability of sets of L20 sequences to sequential machines; This will be the subject of the present chapter. I x Definition 2. An input-output sequence x = '3’ is acceptable to a x state 33. of a machine A if N(sj, x1) = x0. Definition 3. A set, to be denoted by T(Ai)’ of I-O sequences is the' set of acceptable I-O sequences for the state si of the sequential machine A, if all the I-0 sequences in T(Ai) are acceptable to the state 8.1 of the sequen- tial machine A and no other I-O sequence is acceptable to the state si of the s equential machine A. -27- Definition 4. A partial segment ixj of an I-O sequence x = yoyl. . 'Yn-l is the sequence yiyi+1 . . . Yj—l where the yi are input-output pairs. By i’xi is meant the 1—0 sequence % . Definition 5. The number of input-output pairs that make up the I-0 sequence x is called the length of x. Definition 6. The particular partial segment oxi is called an initial segment and thelpartial segment ixn’ where x is of length n, is called a terminal segment. 'Definition 7. A set of 1-0 sequences is initially complete if, whenever an I-O sequence x is in U, then all initial segments of x are in U. That is if 1618 in U, then 0xi is in U for all iSn, where n is the length of x. » Definition 8. A set U of I-O sequences is consistent if, whenever two I—O sequences are in U; which have an initial segment 0xiI of their input sequen- icres in. common, then they both have the same output. sequences 0xi Definition 9. The set of all finite input-output sequences is denoted by T. Lemma 1. Let U be a consistent set of I-O sequences. Define the relation E by xEy, if and only if for all z in T, if xz is in U, then yz is in U and conversely. If E is an equivalence relation of finite index and U is the union of all but one of these equivalence classes, then U is initially complete. -23- Proof: . Since U is consistent one of the equivalence classes must contain those I-O sequences which are inconsistent with the 1—0 sequences in U. Thus, if x is in U xi must also be in U, since Oxi ixn is in U, and ’ 0 must be in one of the equivalence classes different from the one containing inconsistent I-O sequences. Since U is the union of all but one equivalence class x. is in U. 0 1 Theorem 1. A necessary and sufficient condition that a set U of I-O sequences be the acceptable set of I-O sequences for a state si ofa sequen— tial machine A is that U be consistent and the union of all but one of the equivalence classes of the explicit right invariant equivalence relation E of finite index. Proof: Assume that U is the acceptable set of I-O sequences for state 81 of the sequential machine A, that is U = T(Ai)' Since N(si, x10“) = N(si, x1) N(M(si, x1), 0'), the set U is consistent. Since U is consistent, there is only one output sequence associated with any input sequence, thus only the input sequences xI need be consi- dered. Let x and y be any two I-O sequences contained in U. If M(si, x1) = M(Si’ yI) then x and y are equivalent, for if z is any I-O sequence contained in T, such that xz is in U, then M(Si’ szI) = M(M(si, x1), 21) = M(M(si, yI), 21) = M(si, yIzI) and xand yare equi- valent. Since M(Si’ x1) is unique, the set of 1—0 sequences such that M(si, x) 2 sq is either disjoint from the set of I-O sequences such that M(si, x) = sp for p 75 q or both sets are in the same equivalence class. In the latter case sp and 5(1 are called indistinguishable [23, p. 136] . -29- Likewise all non-acceptable I-O sequences are in the same equivalence class because if x is not in U, xz is not in U for any 2 in T. Thus, if A is an 11 state sequential machine, U = T(Ai) is the union of at most n equivalence classes. Assume a set U of 1—0 sequences is consistent and that the given equivalence relation has a finite index and U is the union of all but one of these classes. Since the set U is consistent, U might possibly be the set of acceptable I-O sequences for some state of some sequential machine. A sequential machine A = (S, P), which accepts U, can be con- structed from the equivalence classes. First, let S be the set of all equivalence classes [xi] , [x2] , . . . [Kn—l] of T under E except for that class which contains I-O sequences inconsistent with 1-0 sequences of U. The function P is defined as follows. Let x be any I-O sequence in one of the equivalence [classes contained in U and let (oi, oi) be any input-output pairs. If 3;:- is in an equivalence class contained in U, then P([ x] , oi) = ([xC—cg- ] , oi). Repeating this for all equivalence classes in U and all input-output pairs completely defimess .P. To show that U is accepted by A, we proceed as follows: Denote by si the state corresponding to the equivalence class % containing the null input-output sequence. Let x be any I-O sequence x. is in U. 0 1 The equivalence class [0x1] containing Ox1 is one of the states of A. in U. According to Lemma 1, U is initially complete and -30- . 0 Define: P(si, 0x1) = ([ 0x1], 0x1), P([OXIJ’ 1X2) = ([oxz]: 1X20), . . ., P([Oxn-11’ n-lxn) = “0an n-lxno)° We see that 0x1, 6x2, . . ., 0xn = x are acceptable to the state si of the sequential machine A. Since this is true for any x in U, the sequential machine A accepts the set U of I-O sequences. ' Assume that x is not in U. Then there exists some initial segment 0xi for OS. 1Sn such that Oxi 18 not in U, but 0xi_1 is 1n U. Thus, N(si, 0x11) # Oxio and x. is not acceptable to state 81 of the sequential 0 1 machine A. Since U is complete x cannot be acceptable to state si of the sequential machine A. This shows that state si accepts U and only U, and that U = T(Ai)' As previously mentioned we have been dealing with Mealy's model of a sequential machine. It is interesting to note the differences in the sets of acceptable I-O sequences to a state of a Mealy model sequential machine and those acceptable to a state of a Moore's model sequential machine. Nerode [24, p. 542] has shown that in order for a set U of 1-0 sequences to be accep- table to a Moore model sequential machine it must be "causal". A set of 71-0 sequences is causal if for any x and y in U, if x and y have some initial seg- ment in common then the outputs associated with the next inputs even if the next inputs are different must be the same. That is, if x and y are two I-O sequences such that OXiI = OYiI’ then 0xi.”0 = 0yi+10. Using this fact it can be shown that Mealy's model is more general than Moorels model. Consider the set U of I-O sequences it over the alphabet 2 = {a, b} with output alpha- bet 0 = {11, (3} such that x is in U if and only if x always has a associatdd -31- with a and S with b. This set is consistent and the equivalence relation E is a right invariant equivalence relation of index two. Thus a Mealy model sequential machine can be constructed to accept the set U of I-O sequences. In particular, the sequential machine in figure 3 accepts the set U. (a, a) v (10» (3) Figure 3 This set of I-O sequences, however, is not causal. This can be seen by considering the I-0 sequences a, b and a, a a a, S a, u ment 3 in common but the next outputs are different. Thus there is no Moore These have the initial seg- model sequential machine which will accept the set U. Any set of I-O sequences acceptable to a Moore model is}. however, also acceptable to a Mealy model. The following algorithm, in fact, gives a method of converting a Moore model sequential machine to a Mealy model sequential machine: . Remove all outputs from the states and associate the output which was associated with a state with all input symbols emanating from this state. Figure 4 is a Moore model sequential machine and figure5 is its equivalent Mealy model sequential machine. We have shown that any set of I-O sequences acceptable to a Moore model sequential machine is also acceptable to a Mealy model sequential machine, but the converse is not true. Thus, Mealy's model ofa sequential machine is the more general of the two. -32- Figure 4 Figure 5 -33- It is now appropriate to consider the set of 1-0 sequences that are acceptable to a sequential machine A, if the sequential machine is allowed to start in any state. It will be assumed that each sequential machine A has some state say so, called the connecting state, such that for each si there is an 1-0 sequence x such that M(so, x1) = 9i. Such a machine is called a connected sequential machine. We will also assume that the sequential machine A is in reduced form [3, p. 282]. Definition 10. An I-O sequence x 138 acceptable to a sequential machine A if there exists some state si in S such that N(si, x1) = x0. Definition 11. The set of I-O sequences composed of all and only those I-O sequences acceptable to A is called the acceptable set of 1-0 sequences for A and is denoted by T(A). Let T(AO) be the set of I-O sequences acceptable to the state so. This is the union of all but one of the equivalence classes of the given equivalence relation of finite index. Let us now look at one of these equivalence classes. It represents the set of I-O sequences that terminate in a particular state. Thus, if from each I-O sequence in T(Ao), which has an initial seg- ment which is identical with an I-O sequence of the equivalence class x. is removed, the termi- O 1 nal segment ixn will be an I-O sequence acceptable to the state si of the corresponding to state si, the initial segment sequential machine A. The set of all such terminal sequences is the set of acceptable I-O sequences for state si of the sequential machine A. -34_ Call this set T(Ai)' This set, of course, satisfies the given right invariant equivalence relation over T. If we repeat this process for all states we produce the set of I-O sequences acceptable to each state. Thus, n-l the set T(A) of I-O sequences acceptable to the machine A is U T(Ai)' 0 These ideas are summarized in Theorem 2. Definition 12. The difference of an equivalence class of I-O sequences [x] from a set of I-O sequences U, written U — [x] , is a set of I—O sequences, such that ixn is in U - [x] if and only if 0xi ixn 13 in U and Ox.1 is in [x] . Theorem 2. The set of acceptable I-O sequences for a sequential n machine A is T(A) = U T(Ai), where each T(Ai) satisfies the conditions i=1 of Theorem 1. Also T(Ai) = T(AO) - [x] where 50 is the connecting state and [x] is an equivalence class of T(AO). Theorem 3. Let U be a set of 1-0 sequences. Assume there exists a subset U of U and that the given right invariant relation E separates U 0 0 into a finite number of equivalence classes. Assume also that the differ- ences U.1 = U0 - [XJi’ where [x]0, . . . , [x]n_1 are distinct equivalence classes contained in U, are divided into a finite number of equivalence classes by the given equivalence retétion. Then if U = U Ui and each Ui is consistent then a sequential machine can be constrlu-fted which will accept U. Proof: The sequential machine A is formed by constructing the sequential machine which has some state say so, which will accept the set U0. This machine will then have for its set of acceptable I-O -35- sequences for its other states si the sets T(Ai)' But each T(Ai) = Uo - [XJi' Hence A accepts the set U. Theorem 4. Let U be a set of I-O sequences. U is the set of accep- table I-O sequences for a sequential machine A, if and only if the following three conditions are true. (1) The relation R defined by ny if for all z and w in T, if zxw is in U, then zyw is in U, and conversely, is a congruence relation of finite index. (2) U is the union of all but 1 of the congruence classes of the rela- tion R. (3) Each of the congruence classes contained in U is consistent. Proof: Let A be a sequential machine. Let R be a relation such that ny, if M(si, x1) = M(si, yI) for all si in 5 whenever both M(si’, x1) and M(si, yI) are defined, or both are not defined for the same si. Then R is a congruence relation. The proof of this follows that of the similar theorem for finite automata. . If ny, then x and y must be in the same equivalence class of the right invariant equivalence relation E, and accordingttoTheorem l, the congruence classes are consistent. If there are r internal states in A then for a fixed 1-0 sequence x, M(si, x1) can be any one of r states or be undefined. Thus, the relation R separates T into at most (r-tl)r equiva- lence classes and consequently R is of finite index. Assume that U is the union of all but one of the congruence classes of the given tbflgruence relation and that each equivalence class contained in U is consistent. Let [x] denote a congruence class and let each congru- ence class contained in U denote a state. Define P as follows: if [x] and -36- [y] are two congruence classes, such that [x] contains an initial segment Oyn-l of some I-O sequence Oyn of [y], and if n-lyn is 2—, then P([x ], ai) = ([ y] , 0.1). This, then, completely defines a1 sequential machine A. The proof that U = T(A) is analogous to that of Theorem 1. To this point we have been studying as much of the structure of gen- eral sequential machines as could be distinguished by conéidering only input-output sequences. However, most sequential machines which will be useful in actual switching circuits design have the pr0perty that for any pair of states 8i and sj there is an 1-0 sequence x such that M(si, x1) = sj. Such machines are said to be strongly connected. In the remainder of this chapter we will make use of the characterization of the set of accep- table I-O sequences to prove some interesting properties of strongly connected sequential rm chines and a certain subclass of such machines, positive sequential machine 3 . .Definition 13. Two states si and sj of ‘a connected sequential machine A are equivalent if there exist two l-O sequences x and y such that M(so, x1) 2 8i and M(so, y1) = 3j and both x and y are in the same equivalence class of T under the given right invariant equivalence relation E. This definition compares with that given by Hohn and Aufenkamp [3] . Definition 14. A connected sequential machine is in reduced form if it does not possess any pair of equivalent states. -37- Theorem 5. A connected sequential machine with 11 states is in reduced form if and only if T(Ao), when s is the connecting state, is the 0 union of n equivalence classes of the given right invariant equivalence relation E over T. Proof: Assume A is a reduced connected sequential machine with 11 states. Since A is connected, for any i there exists an I-O sequence x such that M(so, x1) = 81. Since A is reduced, if x and y are two I-O sequences such that M(so, x1) 7! M(s yI), then x and y are in different equivalence 0’ classes. It has been shown that each state corresponds to an equivalence class and that there are n equivalence classes. Assume T(A is the union of n equivalence classes. Since there are I 0) only n states M(so, x1) # M(so, y if [x] is not equivalent to [y]. Thus the sequential machine A is in reduced form. Definition 15. A sequential machine A with 11 states is strongly con- nected if for each i andj (i, jé 11) there exist some input-output sequence x such that M(si, x1) = Sj' Theorem 6. Let A be an n state sequential machine. If for i = l, 2, . . . , n, T‘Ai) is the union of n equivalence classes of the given right invariant equivalence relation E, then A is strongly connected. Proof: Each equivalence class of T(Ai) consists of the I-0 sequences that terminate in distinct states. That is, distinct I-O sequences in different classes of T(Ai) end in' distinct states. Thus, if there are n states and T(Ai) is the union of n classes then there is an I-O sequence x such that -38- M(si, x) = sj forj = 1, 2, . . . , n. Since. this is true for all i, A is strongly connected. This condition is not necessary, for two I-O sequences may termi- nate in different states and still be in the same class, that is if these states are equivalent. For a reduced machine, however, the conditions of the previous theorem are also necessary. Theorem 7. The reduced form of a strongly connected sequential machine i'satstrnng’ly connected sequential machine. Proof: Let A be a strongly connected sequential machine and let 8i and Sj be any two states of the reduced form of the sequential machine A. If 8i and sj are not states which were merged in the formation of a reduced sequential machine then there still exists x such that M(si, x1) = sj. Let either si or sj be a state of the reduced machine produced by the merging of two states of A. Since there exists an 1-0 sequence x such that the function M of one of the states forming si and xI is in one of the states form- . I mg 33., then M(si, x) = sj. Definition 15. A sequential machine A is positive if there exists some r such that for all i andj (i, jé n) there exists an I-O sequence x of length r such that M(Si’ x1) = Sj' Theorem 8. The reduced form of a positive sequential machine is a positive sequential machine. -39- Proof: The proof of this theorem is similar to that of the previous theorem. We have completed one of the major objectives of this study, that of characterizing the sets of acceptable I-O sequences for a sequential machine and have also shown the usefulness of this characterization in proving some theorems concerning the structure of sequential machines. Chapter III INDECOMPOSABLE MATRICES AND THE STRUCTURE OF AUTOMATA The definition of a strongly connected sequential machine was intro- duced by Moore [23, p. 140] and was used by him mostly for the determi- nations of the minimal length experiment necessary to distinguish one machine from another. Weeg and Kateley [ 18] used this idea of strongly connected machines to prove equivalen‘te of a certain class of sequential machines. Seshu, Miller and Metze [21] studied strongly connected machines as such. They made use of connection matrices, which are simi- lar to the connections matrices to be used in this chapter. The concept of a positive machine was introduced by Weeg [26‘] . Its connect ion matrix corresponds very closely to the idea of a primitive matrix studied by Frohenius [7] , Herstein [ 15] , Holladay and Varga [ 16] and others. Various types of matrix representations of sequential machines have been employed in the study of sequential machines. Hohn and Aufenkamp [3] use a connection matrix which has the formal sum of all I-O pairs of the isort (a, o.) in the i j position if P(si, a) = (sj, a). They make use of this representation to reduce a sequential machine to minimal form. Seshu, Miller, and Metze [21] employ another kind of connection matrix called a transition matrix. Corresponding to each input symbol (Ti a transition matrix Ti is defined. If M(si, oi) = s. then there is a one in the i, j th position of T1. If there is no such transition then the i, j th -40- -41- n position is 0. If the alphabet 2 contains exactly the symbols 0-1, oz, . . . , 0' n . then the matrix .C as used in [3] is C = 2 0'1 T1, where addition signifies i=1 Boolean inclusive or. Gill [8] assigns a prime number to each transition and inserts this number in the i, j th position if the transition carries state si to state sj. Weeg [27] used the following definition for a connection matrix which is similar to the transition matrices of Seshu, Metze, and Miller [21] . If for some GP in Z), M(Si’ Up) = sj then there is a one in the ikj th position of the connection matrix C. Otherwise the i, j th position is O. This is the definition that will be employed in this chapter. The connection matrix for the example in figure 1 of Chapter II is: Figure 1 By CI. is meant the rth power of the connection matrix C , where multiplication is the normal matrix multiplication with Boolean arithmetic. The sum of two connection matrices, written A U B, is the elementwise addition with Boolean arithmetic. It is to be noted that the definition of a -42- connection matrix is independent of input symbols and output symbols, thus, the connection matrix and all the theorems of this chapter apply to bothfinite automata and both Mealy's and Moore's model sequential machine. They also apply to precedence matrices for directed graphs, as discussed by Harary [ l4] and others. In common with current literature, the term path of length n from S1 to sj will be used to denote that there exists some input sequence x of length n such that M(si, x) = Sj' It is to be notdd‘that a l in the i, j th position of Cr means that there is a path of length r from si to Sj' Definition 1. A sequential machine is strongly connected if there is a path from each state to each other state of the sequential machine. Definition 2. A connection matrix is strongly connected if the sequen- tial machine which it represents is strongly connected. In the remainder of this chapter the terms connection matrix and the sequential machine which it represents will be used synonymously, and the rows and columns will be used synonymously with the states they represent. A necessary condition that a connection matrix be strongly connected is that it have a non-diagonal l in each row and in each column. For suppose some row does not have an off diagonal 1. Then there is no path from this state to any other state. If there is a column without any off diagonal ones, then there is no path which terminates in this state, and thus there is no path to this state from any other state. This condition is -43- not, however, sufficient. As can be seen from the connection matrix of figure 2, it is notpossible to havea pathfrom state s4or ssto 81’ 82’ or $3. 0 l 0 0 O 0 0 l 0 0 l O 0 0 0 0 0 0 O l 0 0 0 l 0 Figure 2 The connection matrix in figure 1 is strongly connected, as there is a path of length 5 passing through each state. Definition 3. An n x n connection matrix C is indecomposable if there is no permutation matrix P for which where All and A2.2 are square submatrices. (A12 may not be square). Theorem 1. An 11 x n connection matrix is strongly connected if and only if it is indecomposable. Proof: The transformation P C PT corresponds to a permuation of the numbers assigned to the states. But the property of strongly connectedness -44- is independent of the numbering of the states. Now if C is decom- posable as PCP A22 then there can be no path from any state corresponding to the rows of A22 into any state corresponding to the rows of All' Hence C would not be strongly connected. On the other hand, suppose that the n x n matrix C is not strongly connected. Then there is some set 8' of p