THE UNIVERSITY OF MICHIGAN SYSTEMS ENGINEERING LABORATORY Department of Electrical Engineering College of Engineering SEL Technical Report No. 20 COMPUTER PROGRAMS DEALING WITH FINITE STATE MACHINES: PART II by Thomas F. Piatkowski July 1967 This research was supported by United States Air Force Contract AF 30(602)-3546.

TABLE OF CONTENTS Section Page I. Introduction 1 II. Conventions 3 III. Simple Adaptive Diagnosing 4 IV. Finding an Equivalent Regular Expression 32 V. Displaying the Lattice of SP Partitions 49 VL Bibliography 71

I. Introduction During the past several months I have been able to program a number of algorithms dealing with finite-state machines; the purposes of this effort being: (1) pedagogical application, (2) the stimulation of insight, and (3) the generation of new questions and approaches. Out of a set of thirty-eight more or less different problems dealing with finite state machines, I selected seven representatives; namely: 1) simulate a given machine, 2) determine if a given machine is strongly connected, 3) determine the state equivalence classes and minimal form for a given machine, 4) determine the automorphisms and their group for a given machine, 5) determine a shortest simple adaptive diagnosing experiment for a given machine and admissible set, 6) determine an equivalent regular expression for a given machine, 7) exhibit the lattice of SP partitions for a given machine. This report, the second of two, describes the programs treating problems five through seven; the first report treating problems one through four appeared previously.

Concurrent with my own programming efforts, I attempted to document existing programs in this area; the results of my search are included in the bibliography. The first two programs contained in this report are written in 7090 SNOBOL for execution in the batch mode; the third program is written in 360 FORTRAN IV for execution in the time-sharing mode on MTS, the Michigan Terminal System. A conscious effort has been made to make them straightforward and easy to use.

IL Conventions We will deal with N, P, Q machines where N = the number of states in state set S, P = the number of symbols in input alphabet AI, Q = the number of symbols in output alphabet AO. We will only consider machines coded such that S = {1, 2,..., N A ={1,2,...,Q} A machine is a system M =<S, AI, AO, FS, FZ > where S, AI, and AO are as above and where FS, the next state function, maps S x AI - S and FZ, the output function, maps S x AI O A0 for Mealy machines and S - AO for Moore machines. It is assumed that the reader is familiar with the necessary theoretical concepts of finite-state machine theory [See 1, 2, and 3] and with the programming languages SNOBOL and FORTRAN IV. The first two programs were written to run in SNOBOL under the University of Michigan Executive System for the IBM 7090 Computer as it existed in May 1967. The third program was written to run in FORTRAN IV under the University of Michigan Terminal System for the IBM 360 as it existed in July 1967.

III. Simple Adaptive Diagnosing A. Program Name: SAD B. Purpose: To analyze a given finite-state machine and admissible set and determine if a simple adaptive diagnosing experiment exists; if one does, display a representative from the class of shortest such experiments (the length of an experiment is defined here as the length of the longest input sequence required - i. e. the worst case). C. Method: The method of solution consists in properly creating and interpreting a diagnosing tree. The tree has AM, the admissible set, associated with its root node. Branches and nodes are added and deleted by alternate application of growing and pruning algorithms until each branch is appropriately terminated; at this point the tree structure will indicate if an adaptive diagnosing experiment exists and if so display the procedure for carrying it out.

Growing Algorithm: Let M be the machine under consideration. Let So, the source set, = {S,' S 2,'.. Sr } c S represents a range of uncertainty in our knowledge of the present state of M; i. e., we know that the present state of M is one of the states in SO but no more. Associate a node with SO; call this node the source node. From the source node extend P branches, each corresponding to a symbol in AIr Terminate each branch with a distinct node and label each node with the corresponding input; call these new nodes the input nodes. From each input node extend Q branches, each corresponding to a symbol in Ao. Terminate each branch with a distinct node and label the node with the corresponding output; call these new nodes the successor nodes. Each successor node is derived from the source node by a unique input, I, and output, J; therefore we can speak unambiguously about the I/J successor node of the source node for all 1 < I < P and 1 < J < Q. With each I/J successor node associate an I/J successor set as follows: 1) I/J successor set of SO = {FS(s, I) I s e S, FZ(s, I) = J}. In other words, the I/J successor set of SO is the set of all states in M such that each can be reached from a state in SO on the single input I with accompanying output J. Contrary to the usual convention in set theory, however, explicitly indicate multiple non-distinct entries

in any successor set by listing these elements more than once; i. e., if two or more states in SO go into the same state s' on input I with output J, then s' will appear two or more times in the I/J successor set of So. For example, Figure 2 illustrates the above construction for machine M1 (Figure 1) and source set {1, 2, 3}. The growing algorithm displays the possibilities for altering the range of uncertainty in our knowledge of the present state of the machine by applying a single input and monitoring the attending output; i. e., if the present state of the machine is known to be in the source set then if input I causes the attending output J, the new state of the machine must be in the I/J successor set of the source set. Successor Node Evaluation: Application of the growing algorithm results in P x Q successor nodes for each source node. The successor set corresponding to each successor node can be either 1) empty 2) a singleton 3) multiple with distinct entries, or 4) multiple with at least one repeated entry.

7 Figure 1. M1, a 7,3,2 Machine of Source Set {,2,3} for M 1

An empty I/J successor set implies the impossibility of getting an output J when input I is applied to any state in the source set. Such successor nodes and their corresponding branches are deleted from the tree without consequence. A singleton I/J successor set implies that a unique state in the source set yields output J in response to input L In the event this unique state was indeed the initial state of M the inputting of I with attendent outputting of J would identify the fact. Nodes corresponding to singleton sets are terminal in that no further experimenting is needed to identify the machine's present state and its predecessor state in the source set. A multiple distinct I/J successor set implies that if the initial state of M is in the source set and the inputting of I is attended by output J, then the range of uncertainty in the new present state of M is shifted to the I/J successor set with no introduction of ambiguity in the predecessor state; i. e., each state in the I/J successor set has a unique predecessor in the source set and therefore the ability to diagnose the successor set would ensure the ability to diagnose the initial state in the source set, conditional on the original I, J input/output pair. Nodes corresponding to multiple distinct I/J successor sets are not terminal since they indicate some uncertainty still exists in our knowledge of the machine's present state;

in general this range of uncertainty is different and possibly reduced from the range of uncertainty in the source set. A multiple repeated I/J successor set implies that at least two states of the source set yield identical outputs and move to identical successor states in response to input I; such a condition precludes the distinguishing of the initially distinct states by any further experimenting; thus input I must not be applied to M when the range of uncertainty is the source set since doing so will, in general, prohibit a successful diagnosis. For this reason nodes corresponding to multiple repeated I/J successor sets are terminal. Node Logic: The source set is diagnosable iff there exists at least one input I such that for all outputs J, the I/J successor sets are either empty or diagnosable. In other words, source nodes act as OR gates and input nodes as AND gates. This may be indicated explicitly in a graphical presentation of the diagnosis tree by drawing source nodes as $ and input nodes as 0. Furthermore, singleton sets, being always diagnosable, are interpreted as terminal TRUE nodes; multiple repeated successor sets, being never diagnosable, are interpreted as terminal FALSE nodes and both TRUE and FALSE terminal nodes have the usual implication on the truth value of preceeding AND and OR gates.

Erecting and Pruning the Tree: The tree is created by erecting successive levels of successor nodes corresponding to all input strings of length 1, then 2, then 3, etc..... The process is initiated by associating AM, the admissible set, with the single source node at level zero. The first level of successor nodes is erected from the root and then, in turn, provides the source nodes for erection of the second level of successor nodes and so on. In general each level of successor nodes will contain a number of terminal nodes - some TRUE, some FALSE; as each terminal node is created the implication of its truth value is projected as far as possible back through the tree toward the root node. An efficieney of computation is effected by accompanying the backward implication of each new terminal node with the following pruning procedures: 1) If an AND node is TRUE then its preceeding OR node is also TRUE and all portions of the tree descending from the OR node save for the branch to the TRUE AND may be deleted without affecting the truth value of the OR node. 2) If an OR node is FALSE its implication of the truth value FALSE backward toward the root node will halt either at the root node itself or at some AND node which we will call the parent node (a FALSE OR always implies the preceeding AND is FALSE thus backward

implication cannot halt at an OR node unless it be the root). In the latter event delete the parent node, its descendent subtree and the branch descending into the parent node; none of these deletions affect the evaluation of the OR node preceeding the parent node. In general a single TRUE terminal node may induce several applications of rule 1 whereas a single FALSE terminal node will induce only a single application of rule 2. Cycles: There is one additional condition under which a successor node is terminal FALSE; i. e. when its associated set is identical to that of one of its predecessors (not necessarily the immediate predecessor); this follows from the observation that no diagnostic purpose is served by allowing an input/output sequence that causes the range of uncertainty to repeat. Since each input/output sequence corresponds uniquely to its final successor node, the negation of a particular cyclic successor node will eliminate from consideration precisely the proper input/output sequence without of itself eliminating any other sequences. A cyclic terminal node has the same backward implications in the tree as any other FALSE node.

Addition of Initial State Information to the State Sets: Every state set corresponding to a node in the tree explicitly denotes the range of uncertainty in the present state of the machine after a particular input/output sequence. No explicit information is given regarding the range of uncertainty in the initial state of the machine. This information may be explicitly added in the following manner: each state s in the state set under consideration is an I/J successor of some unique initial state s' in the admissible AM; replace the element s in the state set by the state pair s. s' - thus the sets associated with nodes in the tree will be sets of state pairs, the first state in each pair denoting a possible present state and the second denoting the corresponding initial state. For example, in Figure 2 the root node would now have the associated state set {1. 1, 2.2, 3. 3} and the 2/1 successor of the root node the associated state set {4.1, 5.2, 5.3}, etc... The explicit denotation of the initial state associated with each present state is conveniently expedited by modifying equation (1) to read (2) I/J successor set of SO = {FS(s, I). s' s. s' e So, FZ(s, I) = J} Thus the initial state information is created as each successor set is created with reference being made only to the source node involved.

The explicit display of initial state information in the state sets in no way influences the growth of the tree; i. e. the evaluation of terminal nodes, whether singletons, multiple repeated or cyclic depends only on present state information. Termination and Interpretation of the Computation: Construction of the tree is carried out until the truth value of the root node is established; if this value is FALSE no adaptive diagnosing experiment for the given machine and admissible set is possible; if this value is true then an adaptive diagnosing experiment does exist and is carried out as follows: 1) Obtain a copy of the given machine with initial state in the admissible set. 2) Let the first source node be the root node of the tree; i. e. before any input has been applied to the machine the present state and initial state are identical. By assumption this node is TRUE. 3) The source set displays the current range of uncertainty in the present state and the associated initial state of the machine. If the source set is a singleton the present and initial states of the machine are known precisely, the experiment is complete, halt; if the source set is not a singleton go to 4).

4) The pruning algorithm and node logic guarantee that each non-terminal OR node in the tree has a unique TRUE successor input node; in particular the current source node has a unique TRUE successor input node with associated input L Apply input I to the machine and note the output J. Let the I/J successor of the source node become the new source node; this node must be TRUE or else node logic would require the preceeding AND node to be FALSE which would be a contradiction. Go to 3). For example, Figure 3 displays the completed diagnosing tree for machine M1 with AM = S; the positive result of this example ensures that any admissible set is diagnosable in M1. D. Language and System: The program is written in SNOBOL (31 December 1965 version) for execution on the University of Michigan Executive System for the IBM 7090 computer as it existed in May 1967. E. Input: The input deck consists of an arbitrary number of sub-decks; each sub-deck names and describes a finite-state machine and lists one or more admissible sets to be diagnosed for the given machine. The

( 1{t4,2., 3.3,44,4.5, 6.6,7. 7} INPUT 3 o0uP7r V= o LIT PVT = { Z.Z,.3,5.4,4.5, 6.6 INPUT=l OUTPLUT 1 OUTPUT=2 1 1.1,2.,.6 + 4 t3.3,7f.4,6.5} INPT= 2. I NPVT= rP 1 _ \_,,, -- ourr - ou'rPuor 1 OVTP~r=z i4.1r5s.z ~ T t + t3.3,6.A ouT PR= 2, oUTPUT 1 ouVTPUT. {6 ~,v.z}')3 c O&TPrT=i OUTV= 2. Tm OT oIPU%:'l ouItP~ =A Figure 3. Completed Diagnosing Tree for M1, AM = {1,2,3,4,5,6,7}

make-up of each sub-deck and the card formats are as follows: 1) Name card - up to 80 columns are available for any string of alphameric characters identifying the machine by name; trailing blanks are ignored. This card must head each sub-deck even if the name is blank. 2) N, P, Q card - gives the values of N, P, Q for the machine; three integers separated by commas, no blanks, left justified on the card. 3) Transition table cards - N cards, each of the following form: s, s1/jV, s2/j 2,p/fs.jp where s, si, i are integers separated by comma and slash as above and all data is left justified with no blanks and where sE S s. = FS(s, i) ji = FZ(s, i) There should be precisely one transition table card for each state in M; the transition table cards may be in any order provided the last card has s = N. The transition cards provide the capability of describing any Mealy machine;

17 Moore machines may be described by the artifice of making FZ(s, i) independent of i. 4) AM Cards - an arbitrary number of cards, each specifying an admissible set to be tried on M and each in the following form: (s1, s2,.., sm), where the si are integers separated by commas, s1 is preceeded by an open parenthesis in card column 1 and sm (m < N) is succeeded by a closed parenthesis; the parentheses enclose no blanks. Each sub-deck must contain at least one admissible set and each admissible set at least one element. Restrictions: The only limitations on the size of machines (i. e., N, P, Q) or admissible sets that this program will handle are those imposed by the SNOBOL compiler itself on string length, number of strings, etc..... However, the input routines for this program expect to find each of the following data entries on a single card 1) the machine name 2) the N, P, Q data 3) each row of the transition table 4) each admissible set If multiple card input is required the input routines can be

rewritten; no change should be necessary in the body of the program. F. Operation and Output: The program works through the data deck sub-deck by sub-deck and for each will output a description of the corresponding machine followed by a result for each admissible set. If no adaptive experiment exists for a particular admissible set a comment to that effect is made; if an adaptive experiment does exist then the diagnosing tree is listed in the following manner: Each of the non-terminal OR nodes are listed (each is identified by number). The zero node is the root node of the tree. Let X be the number of any OR node in the tree; listed with X in the output is 1) the associated state set indicating the range of uncertainty in the present and initial states, 2) the input I associated with the succeeding TRUE AND node (for each X this is unique), and 3) a list of successor OR nodes corresponding to the various outputs - this list has entries of the form

J/X' where J is an output symbol and X' is the number of the I/J successor to X. Terminal nodes will not be referenced by number, instead the entry'STOP' followed by the initial and final states associated with that terminal node are given after the output. The program does not reuse node numbers that have been pruned away - thus the completed tree and therefore the output list will, in general, not number OR nodes consecutively. The output listing conveniently indicates how to perform a diagnosis; the procedure is to start at node zero, apply the associated input, observe output, move to indicated new node, apply associated input, etc.... until a'STOP' is encountered - at which point the diagnosis is made. At any point along the way the state set associated with each node gives the present range of uncertainty in both the present and initial states.

G. Sample Data 7)'2.7/2f"3/1-. //I,,2 8) / 9 it 2, 39 4,o599,7)...., ) 11' /1, 7 /1, 6/'1/ 3/ I,3/1 0000000D000u00000000000000000000000000000 1 2 3 4 5 6 7 8 | 11 t2 a 14 a X n a is 2122 23242s221 n 293031 3233 343536 373o4l442 43 44 4c5 4647 re i a52 53 4 56 57 1 62 6s64 a 6 a s 0nn72 717, 222222222222222222222222222222222222222222222222222222223222 l222222222222222222 3333333313333333333 333333 3333333333 1:444444444444444444444444444444444444444444444444444444444444444444444444444444_ 5555555555555555555555555555555555555555555 77777777777777777711777777 777777771.7 777777777 7.7 777 7 7 7 7777 7 7 7 777777777 77 7 7 X 777 7 81888080808881880800088880008808888888 0 999999999999999999999999999999999199999 000091 0009909909998099990900009 _ I 1 1 1 0 1 5 1 1 1 It 20 1 2223425627232 29323334336373394 41 4214?441s4516147431 554sosV 679061111116s 59 C1 14667671747577 11 7911 2u2222222 2 222222

21 H. Sample Output SIMPLE ADAPTIVE DIAGNOSING MACHINE NAME _ Ml N = 7, P = 3, Q = 2 TRANSITION TABLES***.S ATE FOLLdLDU BY LIST GF (NEXT STATE/OUTPUT) FOR SUCCESSIVE INPUTS __1 1/,4/1 __.. 2 2/1,5/1,2/1 3 3/2,5/1,3/1 4 6/2,5/1,5/1 5 7/2,4/1,4/1 6 7/1,6/1,0/1 7 6/2,7/,(l/2 _MACHINE NAME = MIr ADMISSIBLE SET = (1,2,3) THE FOLLOoING IS A SIMPLE ADAPTIVE CIAONUSING EXPERIMENT FOR TFE GIVEN MACHINE AND ADMISSIBLE SET NO SET INPUT, FOLLOWED BY THE (L;JTPUT/NEXT NO) LIST O 1.1,2.2,3.3 1 1/1 _ __ 2/STOP(INIT = 3,FIN = 3) 1 1.1,2.2 2 /3 3 4.1.5.2 1 2/4 4 6.1,7.2 1 1/STOP(INIT = 1,FIN = 7) 2/STOP(INIT = 2,FIN = 6) MACHINENAME_ Ml, _AOMISSIBLE SET = (1,2,3,4,5,6,7) THE FCLLOWING IS A SIMPLE ADAPTIVE DIAGNOSING tXPERIMENT FOR THE GIVEN MACHINE AND ADMISSIBLE SET NO SET INPUT, FOLLOWED BY THE (OUTPUT/NEXT NO) LIST O 1.1,r2.2,3.3,4.45.5,6.6,7.7- 3 1/2 2/STOP(INIT = 7,FIN = 7) 2 1.1,2.2,3.3,5.4,4.5,6.6 1 1/4.2/5 4 1.1,2.2,7.6 2 _ 1/8 2/STOPIINIT = 6,FIN = 7) 5 3.3,7.4,6.5 1 1/STOP( INIT = 5,FIN = 7) 2/13 8 4.1,5.2 1 2/19 _ _ _13 3.3,6.4 1 __ _ 1/STOP(INIT = 4,FIN = 7) 2/STOP(INIT = 3,FIN = 3) 19 6.1,7.2 1 1/STOP(INIT = 1,FIN = 7) 2/STOP(INIT = 2,FIN ='61

22 SIMPLE AUAPTIVE CIAGNOSING MACHINE NAME = A21GILLPAGE 1UE N = 10, P = 2, C = 2 TRANSITION TALtES***SIATE FULLOWiED BY LIST CF (NEXT STATE/OUTPUT) FOR SUCCESSIVE INPUTS _1.._.5/1,1/1 2 6/1,2/1 3 7/2,3/1 4 8/2,4/1.5 9/1,0/1 6 9/1,7/2 _.1_ _.....6/ 2, 10/ 1 8 7/1,10/1 9 g/1,9/2 10 10/2t10/1 MACHINE NAME = A21,1GILL,PAGE!0o, ADMISSIBLE SET = (1,2,3,4) THE FOLLOWIN6 IS A SiMPLE A0APIVE GIAGNOSING tXPERIMENT FOR THE GIVEN MACHINE AND ADMISSIBLE SET NO SET INPUT, FOLLUiW[ BY THE (OUTPUT/NEXT NO) LIST O 1. 1 2.2,3.3.4 1 1/1 2/2 1 5.1,6.2 2 1/STJP'(INIT = I,FIN = 6) 2/STOP(INIT = 2tFIN = 7) 2 7.3,8.4 1 1/STUP(INIT = 4,FIN = 7) 2/STUP(INIT = 3,FIN = 6) MACHINE NAME = A21,GILL,PAGE 106, ADMISSIBLE SET = (5,6,7,8) NO SIMPLE ADAPTIVE DIAGNOSING EXPERKIMtNT EXISTS FOR THE GIVEN MACHINE AND ADMISSIBLE SET MACHINE NAME = A21,GILL,PAGE 106, ADMISSIBLE SET = (7) ADMISSIBLE SET IS A SINGLETON***NU EXPERIMENT NECESSARY **** ALL INPUT DATA HAVE BEEN PROCESSED ELAPSEtD TIME -- TOTAL PROCESSING EXECUT I ON LOADING 0' 21.8" 0' 2.C" O' 14.3" O' 5.5"

23 I. Important Program Variables: This portion of the report will use the conventions of SNOBOL to describe the contents of several important string variables appearing in the program. OR nodes: each OR node is identified by a number, say X. Associated with each OR node is a string'OR' X which contains information on that node and its function in the tree. The contents of'OR' X will vary during execution as follows: 1) if node X is pruned from the tree then $('OR' X) is null, 2) if node X is terminal TRUE then $('OR' X) ='F' FIN'I' INIT'O' OUT where FIN = the associated final state INIT = the associated initial state OUT = the associated output symbol, 3) if node X is nonterminal TRUE then $('OR' X) ='PT' SET'0' OUT'S' Z',' where SET = the state pair set corresponding to node X and will be of the form #. #, #. #,..., #. #, OUT = the associated output and Z = the number of the unique succeeding AND node

24 4) if node X is of undetermined truth value $('OR' X) ='L' LG'PT' SET'PR' Z'S' LIST where LG = the number of elements in SET (which is defined as in 3 above) Z = the number of the immediate AND predecessor of X LIST = a list (of the form #,#,..,#,) of the AND successors of X (all must be unvalued) AND nodes: each AND node is identified by a number, say Z. Associated with each AND node is a string'A' Z which contains information on that node and its function in the tree. The content of'A' Z will vary during execution as follows: 1) if node Z is pruned from the tree then $('A' Z) is null 2) if node Z is TRUE then $('A' Z) ='I' IN'UT' LIST where IN = the associated input symbol and LIST = the list of TRUE successor OR nodes (in the form #, #,...,#,) 3) if node Z is of undetermined truth value $('A' Z) ='I' IN'PR' X'U' LIST1'T' LIST2

25 where IN = the associated input symbol X = the number of the immediate OR predecessor LIST1 = the list of unvalued immediate successor OR nodes and LIST2 = the list of TRUE immediate successor OR nodes AD = the list of AND nodes that should be pruned from the tree, in the form #,#, #.., AM = the list of admissible states, in the form #, #,...,#, $('FS'"'' ) = FS(S,I) $('FZ'tS'.' I) = FZ(S,I) NAME = the name of M NAND = the number of the next AND node to be created NOR = the number of the next OR node to be created OA = the list of the nonterminal OR nodes with as yet uncomputed successors, in the form #,#,...,#, OD = the list of OR nodes that should be pruned from the tree, in the form #,#,...,#,

26 During the construction and testing of all I/J successors of an unvalued OR node the following temporary strings are created. OAT = the list of information on nonterminal OR node successors to a new AND node, each entry in the list is of the form NO'L' LG'PT' SET'O' OUT'PR' Z'S' where NO = the number of the new OR node and the remainder of the entry is as previously defined for a nonterminal OR node. OS = the list of new AND node successors SSW = the program switch which indicates the truth value of the OR node whose successors are being created SW = the program switch which indicates if a successful experiment has been found TT = the list of information on TRUE terminal OR node successors to a new AND node, each entry in the list is of the form NO'F' FIN'I' INIT'O' OUT'/' where NO = the number of the new OR node and the remainder of the entry is as previously defined for a terminal OR node.

27 Y = the current I/J successor set being examined, in the form #. #, #. #,..., #. #,

J. Annotated Flow Chart STAF~~~~~~~~~~~~~~~~T ~ ~ ~ INPI.K KAMEqNSPqQ LOAD lRp O, 0M-, i ST'TERM ON 8A, Pe~ N EKIST. eS = PS AND FZ-TABLFS; A|r O V eT Gsw= SW CHASt. PRINT 1AME, ",P,Q. F3 AUN FM-TABLES 1 N C..ASE FALSE BAc ADLP eS T BRACNH 8, SSW =Il ~TWAI7 RPee' NGD.E; If INPUT AMi 1 LE^T N' HIHGEST FALSE C4ASEF F Pkiw AM IeR NODE, X- x4.1H.,TES PFALSE AV40 V401 Q ~l~~~~~~ t |1 LEASp|CREEA'E'A NAND; C VEAE NW eP I I-l F IINevES -Rem -M ADD ANP ASSUCc eAST = |F _ | e eR'N 5 INCREMENT NAND;SET AD \ NIO?!F AD)D Y,'le ADe f i; FSh-' SWrSJ='INEADAD, A -esi; ClAAS FEE R BAC K'eWARe D ser sW=1 ROOT NODE ADruJU BeRNBE nC: rl PRitiT'AM = I~w/SE succ e.DEUCJ J~~~ T Am ON SYSI a- fF SUc' OF GLEF( LEST NeISTiERM eR'A' /'ANd=i T NrNExre e w~G AfT DELETE i ADD GATTG 4 eA., ADD SUC'S eF CR|EATE NEW GI FALSE | LET N-4 SgM? 7',4A Ne Te eD; | ES FROM. OA, y eN IeT', DELETE; |D=4? DELETe %A,1 H | PELETE; |_ B(= SUC e N) | 1 F | CREATE NEW9R | UE OUN"N =0 i NPU l; F PRLN1T 1LES;| F NMDES FFJiM PT-; T PRINT'iR' N I -l SET eT I LD? AD: AT s; ~ET NB~~ST 7ekll~P NAND Te e8; ADoSucc I a -e | V, veDETE; SET S:W= UNKB | tt EXP? |- T,6RDER Se)CCpI S @ r. _. AD SUcS ep IN 1 MEII' bY eUTPUTS ANgD |eN SW M we "'re AP | AND 6RINT E& LRN o I~~~~~~~~~pcr Le.'w -........ I! ].ex'TeA 8 ~EB ~PE I I~~~~~~~.................... If I I CPL EMET NED.| I _.........................................................................

29 K. Annotated Program Listing SNOBOL (31 CEC i965 VERSION) PRGGRAM LISTING. _ _AL T _R _ NUM_=' 0123456789.' NEXTM NAME = TRIM(SYSPIT) SYSPOT ='lSIMPLE ADAPTIVE DIAGNOSING' SNSPOT =' SYSPOT ='MACHINE NAME =' NAME SYSPOT =' TRIM(SYSPIT) *N*'t',P*',' *Q* SYSPOT ='N =' N', P =' P', C ='Q _S.PGT =' SYSPOT ='TRANSITION TABLES***STATE FOLLOWED.'BY LIST OF (NEXT STATE/UUTPUT) FOR SUCCESSIVE INPUTS' SYSPOT =' I NEXTX.T_ RLM(iSeYSPITl) *.* I,',,. *LI ST* SYSPOT ='' X'' LIST LIST ='LIST',' Y ='O'... NEXTY Y = Y +'I' LIST *STATE*'/' *OUTPUT*', = _ _ $('FS' X'.' Y) = STATE $('FZ' X'.' Y) = OUTPUT.EQ(Y,P) /F(NEXTY).EQ(X,N) /F(NEXTX) NEXTAM SYSPIT' (' *AM*')''2! SYSPOT ='1MACHINE NAME =' NAME, ADMISSIBLE SET = (' AM')' I SYSPOT = ~'"-~'.EQ('O' SIZE(CELETE(AMNUM))) /S(SINGLE) AM= AM',' ___ ORO ='L' SIZE(DELETE(AMNUM)),'PT' MORE AM *STATE*',' = /F(NOMORE) ~A1...... ORO = ORO STATE'.' STATE',' /(MORE) NOMORE ORO = ORO'OPRS'........- - ~OA ='0,' NCR ='1' NAND =' Il''5,- NEXTOA OA $N*'f = 6 Lii( EOXTOR' N)'L_ *LG*'PT' *PART*'O'0 *OUT*'PR' *PRED*'S' /F(NEXTOA) OS = SSW ='CHASEF' NEWI TT = O AT = _ _ _ _ __ _ _ _='1' NEWJ Y = PT = PART 7 NEXTP PT *STATE*.'. *INIT*',' = /F(SKIP).NE(J,$(' FZ' STATE'.' I)) S(NEXTP) _ __ _ =Y $('FS" STATE'.' I)'.' INIT',' /(NEXTP)

30 F _SK. IP......EQUALS(Y, ) /S(NEXTJ) LGY = SIZE(DELETE(YNUM} } ~..~EQ(.LGY,' l' 3 /S(YTRUE} YT =',' Y YT',' *STATE*'. *JUNK*'t' STATE'.' /SNEXTI ) 40 NP = N TESTF $(' OR' NP)'L' *L*'PT' *PRT*'O' *OT*'PR' *PRD*'St. EQ(L.LGY) /F(ADDY) AGAIN PRF *STATE*'.* JUNK*' = /F(NEXTI) (, y),' STATE'.' /S(AGAIN) ADUY OAT = OAT NOR'L' LGY'PT' Y'O' J'PR' NAND'S' 1./ ( NEXTNOR) YTRUE Y'*FIN*' *'o INI' - TT = TT NOR'F' FIN'I' INIT'O' J''/' 41- NEXTNOR NCR = NCR +'1' 4 NEXTJ.EQ(Jt,) /S(ANDCK) J = J +'I' /(NEWJ) A__ NEXTI.E( I,P) /S ( $SSW )'.-6 I = I +'1' /(NEWI) __ CHASEF.EQ(N,'O' ) /S(NOEXP) f- $('GR' N)'PR' *X:'S' 1 4('A' X)'PR' *N*'U' |i('LR' N)'S' *SUCC* ECUALS(SUCC,(X',')) /S(CHASEF) AD = X',' SW ='NEXTOA'.... - -' SUCC =',' SUCC 1:8 SLCC',' X',' =',' SUCC'' = Si $('OR' N)'S' *JUNK* ='S' SUCC /(ADJUST) 19 ANDCK EQUAL S(OAT, ) /S ( ANDT ) i $('"A' NAND) = I' I'PR' N'U' _ SUCCUN OAT *NUS*'L' *JUNK*'S' = /F(SUCCT) UA = OA NUS',' $('OR' NUS) ='L' JUNK'I' $('A' NAND) = S(' A' NAND) NUS',' /(SUCCUN) 20 SUCCT S('A' NAND) = $('A' NAND)'T' NEXTSC TT *NT*'F' *JUNK*'/' = /F(ENDTT) S('OR' NT) ='F' JUNK S('A' NAND) = $('A' NAND) NT',' /(NEXTSC) ENDTT OS = CS NAND',' IL. -___ SSW =' UNK' NAND = NAND +'1' /(NEXTI).ANDT $('A' NAND) ='I' I'UT' NEXTT TT *NR*'F' *JUNK*' = /F(NOT) $('OR' Nk) ='F' JUNK $('A' NAND) = $('A' NAND) NR',' /(NEXTT) NOT $(' OR' N) ='PT' PART' O' OUT' S' NAND',' NAND = NAND +'1' AD = CS _,_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _A = ___.S........i C S CHASET' A' PRED)'I' *INP*'PR' *ANDP*' U' *UN*'T' *TR*. ____/F ( EXPOUT).. Z2. EQUALS(UN,(N',')) /F(ANDUN) _~.~ —21............... $('A' PRED) ='I' INP'UT' TR UN $('OR' ANDP)'L' *L*'PT' *SAVE*'PR' *ORP*'S' *SUCC* = PT' SAVE I S PRED'i. _._ _ TRYX SUCC *X*',' = _____........ - EQ(XIPRED) /S(AODS) SUCC = SUCC X',' /(TRYX) ADDS AC = AD SUCC N = ANDP PRED = GRP /(CHASET) ANDUN UN *X*',, = __ __.......... EQ(XN) /S(ADDUN) UN = UN X' t/(ANDUN)',ADDUN $ _ _ s SA' PRED) ='' INP'PR ANDP'_U'_ UN'T' TR X_

31 23 _ _ SW =' NEXTOA' /(ADJUST) 24A- EXPOUT SW ='EXP' 25-0 ADJUST AD *NO*',' = /F(ORCK) 26 $('A' NO) *JUNK*'U' *UN* iT' *TR* = UC = 00 UN TR /(ADJUST) 2'-f ORCK U~ *NO*',' = /F(FINCK)._......._ $('Uk.' NO) *JUNK*'S' *SUCC* = /F(ORT) 30 28 AU = AD SUCC /(ORCK) ____ORT $('OR' NU) = I(ORCK 29-'.- FINCK EtUALS(AD ) /S($SW )F (ADJUST) UNK $('UR' N) ='L' LG'PT' PART'O' OUT'PR' PRED.'S' US /(NEXTOA) NOEXP SYSPOT = 32 SYSPOT ='NU SIMPLE ADAPTIVE DIAGNOSING''EXPERIMENT EXISTS FUR THE GIVEN MACHINE AND AUMISSIBLE SET' 35 —-, LOKAM SYSLUK' (' *AM*')' /S(NEXTAM)F(NEXTM) EXP SYSPOT = SYSPOT ='THE FOLLOWING IS A SIMPLE ADAPTIVE *'DIAGNOSING EXPERIMENT FOR THE GIVEN MACHINE AND ADMISSIBLE SET',34 SYSPOT = _ SYSPOT ='NO SET INPUT, FOLLOWED BY',.' THE (OUTPUT/NEXT NO) LIST' _I L~~~~ OT ='O,' 3S — NEXTOR UT *N*',' = /F(LCKAM) __ $('OR,' N)'PT' *PART*',O' *OUT*'S' *SUCC*'t' = $('A' SUCC)'I' *IN*'UT' *TR* = SYSPOT ='' SYSPOT ='' N'' PART'' IN _ NEXTS TR *X*',' = /F(OUTPUT) $('OR' X)'C' *OUT*'S' /F(TRUE) __ ('S' UUT) = X /(NEXTS) TRUE $('OR' X)'F' *FIN*'1I' *INIT*'0' *OUT* = 36 ${'S' OUT) ='STOP(INIT =' INIT',FIN' a FIN')' /(NEXTS) OUTPUT N ='1' NEWN EQUALS($('S' N),) /S(NEXTN) SYSPOT ='' N /' $('S' N) $('S' N) ANCHORI)'S' /S(ERASE).............. __-T=__= CT $('S' N)','.... ERASE $('S' N) __NEXTN.EQ(NQ) /S(NEXTOR) N = N +'1' /(NEWN)........ SINGLE SYSPOT ='ADMISSIBLE SET IS A SINGLETON***'.'NO EXPERIMENT NECESSARY' /(LOKAM) END SUCCESSFUL COMPI LATI ON

IV. Finding an Equivalent Regular Expression A. Program RE name: B. Purpose: To display a regular expression equivalent to the set of input strings accepted by a given Moore or Mealy machine with initial state and accepting output specified. C. Method: Given any finite-state machine one can compute the k regular expression a ij, which denotes all input strings that take the given machine from state i to state j without passing through any state with index > k, via the recursion equation k k-1 k-1 k-1 k-1 ij ij U kik kk )*kj and terminal equations = A u {x FS(i, x) = i} where A is the null string (p = null set) and a = {xlFS(i,x)=j} i j. 0 Notes: 1) Contrary to McNaughton-Yamada a i. can never be the empty set (See Harrison [3], p. 325). 2) ak. is a function only of the set of a's for k-1; thus the k-1 set of a's can be discarded once the k set is known. 32

33 The regular expression equivalent to a given Moore machine with initial state i and accepting output z is U ~f;N aij; FZ(j)=z and the regular expression equivalent to a given Mealy machine with initial state i and accepting output z is U aN3 jz j S where.. {xI FZ(j,x)= z}. In the program being described the recursion equation for evaluating akj is not implemented blindly; rather, attempts are made to identify and exploit simple identities - such as auk = kua = a a* uA= Aua* = a* etc. To assist in this endeavor the program attaches to each a -string a type code selected according to the following scheme (every a-string will be in the form C',' R where C is the type code and R is a regular expression):

34 C Implied Regular Expression PL q (the empty set); R is blank L A (the null tape); R is blank 1 R (R = singleton f A) E A u R (A i R = single string of concatenated RE's) I R (A e R = single string of concatenated RE's) S R ( R = union of several RE's) 1E A U R (A R = singleton) SE A u R (A $ R = union of several RE's) SI R (A e R = union of several RE's) I* R* (R = single string of concatenated RE's) 1I* R* (R = singleton # A) SI* R* (R = union of several RE's) blank R (A' R = single string of concatenated RE' s) Not all simplifications are detected, however, and it is frequently the case that the observant user can further simplify the results this program produces. D. Language and System: The program is written in SNOBOL (31 December 1965 version) for execution on the University of Michigan Executive System for the IBM 7090 Computer as it existed in May 1967.

35 E. Input: The input deck consists of an arbitrary number of subdecks; each sub-deck names and describes a finite-state machine and lists one or more pairs of initial state and accepting output relative to which equivalent regular expressions are sought. The make-up of each sub-deck and the card formats are as follows: 1) Name card - up to 80 columns are available for any string of alphameric characters identifying the machine by name; trailing blanks are ignored. This card must head each sub-deck even if the name is blank. 2) N, P, Q, T card - gives the values of N, P, Q and specifies the type of the machine; three integers and a code word separated by commas, no blanks, left justified on the card. The code word shall be MOORE or MEALY according to the type of machine being described. 3) Transition table cards N cards, each of the following form: s/j, s, s2..., sp for a Moore machine and s, Sl/jI' S2/j2, "'' Sp/jp for a Mealy machine where all data is left justified with no blanks and where s e S

36 j = FZ(s) for a Moore machine Si = FS(s, i) ji = FZ(s, i) for a Mealy machine. There should be precisely one transition table card of the appropriate type for each state in M; the transition table cards may be in any order provided the last card has s = N. 4) Initial state/accepting output card - a single card specifying one or more initial state-accepting output pairs relative to which equivalent regular expressions on the given machine are sought. Data should appear in the following form: S1/Z1,' 2/z2,..., s k/zk where s. e S, z. E A and where all data is left 1' 1 0 justified with no blanks. Restrictions: The only limitations on the size of machines (i. e., N, P, Q) or number of initial state-accepting output pairs this program will handle are those imposed by the SNOBOL compiler itself on string length, number of strings, etc..... However, the input routines for this program expect to find each of the following data entries on a single card:

37 1) the machine name 2) the N, P, Q, T data 3) each row of the transition table 4) the set of initial state-accepting output pairs. If multiple card input is required the input routines can be rewritten; no change should be necessary in the body of the program. F. Operation and Output: The program works through the data deck sub-deck by sub-deck and for each will output a description of the corresponding machine followed by a regular expression for each initial state-accepting output pair. The letter L is used to denote the null string in the output regular expressions.

G. Sample Data /2,4/2. 7/2, 9/2, 5i/2, 8/2/2, 1,9 /1,5 5 /2, 1,6 /2,13,3 ~/1, 3, i /9, 2, 29 MOORE DEMO 1 2 3 4 5 6 7 8 9 10 111 U t3 14 t 17 n t 0 21 2 32 2 5 n 2 n 2 30 31 32 33 343 36 37 3I A 40 41 42 43 44 45 46 47 44 4 50 51 52 S3 54 56 57 s 1 So 60 6 2 3 4 6 U 67 U & 710 71 ) n 4 75 77 7 o 11111111111 11111111111111 1 11111111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1111 111111 1 111111 1111 222222222222222222222222222222222222222222222222222222222222222222l2?2222222222 33333333133333333333333333333333333333333333333333333331333333333333333333333 4,4,4444444444444444444444444 44444444444444 4 44444444444444444 j44444444444444 _ 55,555555555555555555555555555555555555 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 55555 5 5 5 5 5 5 5 5 5 5 5 5 5 5 66666.6666666666666666666666666666666666666666666666666666666666666666666666666 7777777777777777777777777?77777777777777777777777777777777777777777777'7777 8888888888888888888888888888888888888888888888888 8888 8888888888888 99999999999999999 9999999999991 9 999 999 999919999998919989899 8 6 2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 16 19 20 21 22 23 24 25 26 27 26 29'O 31 32 33 6 3 35 36 37 36 39 40 41 4? 4? 44 45 46 J7 6U 3 50 56 %7 53 54 55 S6 57 58 59 60 6 62 6 5 66 67 6 69 u 71 1 73 14 75 76 n 7 7 7 7 77 7 7 II I II I 7 77 7 71 7 7 77 7 17 7 I 77 7 I7 7 7 17 7 77 7 7 77 7 77 7 I 17 7 77 7 7 77 7 77 7 7 77 7 7. I1 7

/21,29 1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /1,r2, 3 /27 3, 2,2, 2IMOORE C NAUOHTOi, YAMADA FIG. 4 /3 3/1 /29 22t 2,3 2,MEALYRE A A~HTON`J YAMOMA F IG. j62 7,"Po 7/2 ~:T/II /11 Li6/1 97/2-)4/li4/1 9~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2/1 15Z/l,2/1 793ys tMEALY! ii A'cii l0l0lllllODOliOOOO2 11100000000 0110902 12202222 3 22 22 220'2011 1 2 5 6 7 8 9 10 11 I' 13 14 1 5 16 1 18 19 10 2! 77 23 24 25 26 21 129 30 31 32 3; 4 35 36 37 38 39 40 41 47 (1 44:5 45 47 48 43;2 4, f, 56 Si'6'i 61, L~i U J 6, Sc: 61' 7 1:379g 11 111 1 1 111lil1 1 1111111 1111 1111 111111111 111111111 111111 1 1 1 1 I _ 2222222222222222222222222222?222222222222222222222222223222222 333323 32' 3323333333f32333333~3323333333323333323 3'33331333333 44444444444444a4444444444444444444444444444444444444444444444 5555555555555555555555555f5555555555555j5555555 55555555555555 6E69932999119919199191371999516969999666966966999991699266666 71117177177777117121121 1211177717711717111111111111217711111211 888a888888l?9882988189911131111118111818819b19918888128a818s ii 1131211711 911 1197 111112171199123112291191191119191 199 22222 2 2 922 22 2 2 232 2 ~2 2 2 2 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 2 2 2 29 2 2 2. 2.2 22 2 2 22 2 2 2 2 2 2 2i 2 2 3 2 222 2 4 2 626 62 2 222 2232.2 2 2 2 222 3 33 33 3 11 3 2 3 33 3 3 2 3 3 3 3!2 3 3 3 3 3 3 39 0) 32 3 33 3 33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3,;~:j 6:~s 3 1 3 3 2 3 3 3 3 3 3 9 3 3 3 3 3 333 4 4 4 4 44 44 44 4 4 4 4 44 44 44 4 4 4 44 44 44 4 4 4 4 44 44 44 4 4 4 44 44 44 4 4 A 4 44 44 44 4 4 4

40 H. Sample Output EQUIVALENT REGULAR'EXPRESSION EVALUATION MACHINE NAME = M DEMO N = 9, P = 2, Q = 2, TYPE = MOORE TRANSITION TABLES***STATE/CUTPUT FOLLOWED BY LIST OF NEXT STATES FCR SUCCESSIVE INPUTS 1/1 1,1. 2./L —..-. 3 3,3 3/2 3,3 4/2 1,1 5/2 1,6 6/1 5,5 7/2 8,1 8/1 9,1 9/2 1 9 MACHINE NAME = M DEMO, INITIAL STATE = 1, ACCEPTING CUTPUtT = 2 EQUIVALENT RE = EMPTY MACHINE NAME = M DEMO, INITIAL STATE = 4, ACCEPTING OUTPUT = 2 EQUIVALENT RE = L MACHINE NAME = M DEMO, INITIAL STATE = 7, ACCEPTING OUTPUT = 2 EQUIVALENT RE = LUI1U112* MACHINE NAME = M DEMO, INITIAL STATE = 9, ACCEPTING OUTPUT = 2 EQUIVALENT RE = 2* MACHINE NAME = M DEMO, INITIAL STATE = 5, ACCEPTING OUTPUT = 2 EQUIVALENT RE = LU2((1U2)2)*(1U2) MACHINE NAME = M DEMO, INITIAL STATE = 8, ACCEPTING OUTPUT = 2 EQUIVALENT RE = 1U12*

EQUIVALENT REGULAR EXPRESSION EVALUATION MACHINE NAME = M1 N = 7, P = 3, Q = 2, TYPE = MEALY TRANSITION TABLES***STATE FOLLOWED BY LIST OF (NEXT STATE/OUTPUT) FOR SUCCESSIVE INPUTS 1 1/ 1,4/1, 1/1 2 2/1,5/1,2/1 3 3/2,5/1,3/1 4 6/2,5/1,5/1 5 7/2,4/1,4/1 6 7/1,6/1,6/1 7 6/2,7/2,7/2 MACHINE NAME = M1, INITIAL STATE = 1, ACCEPTING OUTPUT = 2 EQUIVALENT RE = (2U(1U3)*2U(2U(1U3)*21(2U3)(23(2 U3))*(2U3))1U((2U~lU3)*2)(2U3)UI2U(1U3)*2)(2U3)((2U3)(2U3))*)lUI(2U(1U3*2)(2U3 )( 2U3) (2U3 ) )*lUt( 2U 1U3)*2) lU(2U( 1U3)*2 )( 2U3(2U3)(2U3) ) *(2U3)1 ) (2U3)1U ((2U(1U3)*2 )(2U3)( (2U3)(2U3))*U( (1U3)*2)1U(2U(1U3)*2)(2U3)((2U3)(2U3))*(2U3)1)(2U3)*1!(2U3U1(2U3)*1)*)(1U21U3) MACHINE NAME = M1, INITIAL STATE = 2, ACCEPTING OUTPUT = 2 EQUIVALENT RE = (2U( 1U3)*2) ((2U3)(2U3) )*(2U3) 1U(2U( lU3)*2U(2U(lU3)*2)((2U3) (2U3) )*)1U( (2U(1U3)*2)((2U3)(2U3))*lU(2U(lU3)*2)((2U3 2U3)I*(2U3)l2U3)*1U((2U(1U3)*2( (2U3)2U3(3 )elU(2U(1U3)*2) ((2U3)(2U3) )*(2U3)1(2U.3)*I)(2U3Ul(2U3)*1e*)(lU2U3 MACHINE NAME = Ml, INITIAL STATE = 7, ACCEPTING OUTPUT = I i EQUIVALENT RE = (1UL(2U3)*U(2U3Ul(2U3)*1)*(1U1(2U3)*))(1U2U3) EQUIVALENT REGULAR EXPRESSION EVALUATION MACHINE NAME = MC NAUGHTON, YAMADA FIG. 3 N = 3, P = 29 Q = 2, TYPE = MOORE TRANSITION TABLES***STATE/OUTPUT FOLLOWED BY LIST OF NEXT STATES FOR SUCCESSIVE INPUTS 1/2 2,3 2/1 3,1 3/1 3,2 MACHINE NAME = MC NAUGHTON, YAMADA FIG. 3, INITIAL STATE = 2, ACCEPTING OUTPUT = 2 EQUIVALENT RE = 2U(21)*2U(1U22U(21)*(1U22))(1U2(21)*(1U221)*2(21)*2 MACHINE NAME = MC NAUGHTON, YAMADA FIG. 3, INITIAL STATE = 3, ACCEPTING OUTPUT = 1 EQUIVALENT RE-= 2U2(21)*U(1U2(21)*(1U22))*(2U2(21)*)U(1U2(21)*(1U22))*

42 EQUIVALENT REGULAR EXPRESSION EVALUATION MACHINE NAME = MC NAUGHTON, YAMADA FIG., 4 N = 3, P = 2, Q = 2, TYPE = MOORE TRANSITION TABLES***STATE/OUTPUT FOLLOWED BY LIST OF NEXT STATES FOR SUCCESSIVE INPUTS 1/2 3,2 2/1 2,3 3/1 2,1 MACHINE NAME = MC NAUGHTON, YAMADA FIG. 4, INITIAL STATE = 3, ACCEPTING OUTPUT = 2 EQUIVALENT RE = 2U(21U(1U22)1*2)*2 **** ALL INPUT DATA HAVE BEEN PROCESSED ELAPSED TIME -- TOTAL PROCESSING EXECUTION LOADING 5' 59.1" 0' 1.9" 5' 51.0" 01 6.2"

43 L Important Program Variables: This portion of the report will use the conventions of SNOBOL to describe the contents of several important string variables appearing in the program. $('A','.'J'.'X) = a string of the form C'.' R where C is a type code and R a regular expression; the set of input strings denoted by C and R k is al. $('A' I'.' J'.' Y) = a string of the same form as above which denotes a,. $('FY'S'.' Z) = /SZ = {x FZ(S,x) =Z}, for Mealy machines only. $('FZ' S) - FZ(S), for Moore machines only. PROD = a subroutine which concatenates two given regular expressions; i. e., PROD(A,B) = AB. STAR = a subroutine which stars a given regular expression; i. e., STAR(A) = A*. UNION a subroutine which yields the union of two given regular expressions, i. e. UNION(A,B) = A u B.

44 J. Annotated Flow Chart I @ I PREPARE RE F-R PRII-MING; PRII41 PRINT NAME,$, RY Te PIcK S/7 SET TT OR / RE U'.. J.; X FeR T:= C PReM L, DELETE UNSUCC RE- U A'S..J. r z) VZ Y FG= M-EAY' | ", R EAD L. N1 P, Q T; I PKIT NAAME Lc J/ T et L; L VE;J: A='AFI.'J.y, B= A F.K.YU.. -! (~)INTER.CHANGE C IA' K.K.Y, D IA\K.J.Y SET T- E eR Y X ANO Y A L.J.X = SeRTEST A U (B c*)Dy. =[_ S. |~~ AU 5 (C* D)} PIURNT ITTL' K=X=, Y=O ~ T BRACH 8T ) |A "v PUT EAC.'A.. J0 IN~ ~-) (T - () STANDARD FRM AND READ 3=,ZL, READ SL; ADD T14E PREPER. -PE PRINT S, ZL; PRINT S,L; CEDE; IF M IS A'FE' S -= -. r~''S.'=" MEALY MAC-[\,E De ___E SAMME FPR. FY S.J L - L s |, I /. i'.KNCH GNT PkCc J FReBM'L; DELETE A S.J.O = A5.j.O U I: SCK J/iE FPem L; DELETE; S.Z = 1FY'S._ IU' I

45 K. Annotated Program Listing SNOBOL (31 DEC 1965 VERSION) PROGRAM LISTINGC. DEFINE('STAR(A)','STL','BXY,Z') DEFINE('UNION(A,B)''UN1','CTA,TB,TAB,SA,SB,X,YA,YB,Z,ZA,ZB') DEFINE('PROD(AB)','PRi','C,TATBSASBTABX,Y') START AE ='/OUTPUT' AY = BE ='NEXT STATES' BY ='(NEXT STATE/OUTPUT)' NEWM NAME = TRIM(SYSPIT) TRIM(SYSPIT) *N*',' *P*',' *Q*',' *T* SYSPOT ='I1EQUIVALENT REGULAR EXPRESSION' "Ii.' EVALUATION' SYSPOT = SYSPOT ='MACHINE NAME =' NAME SYSPOT ='N ='N', P =' P', Q =' Q ~', TYPE =' T 2' — ____ T *X/,4'* = SYSPOT ='53~~~~~ ~SYSPOT ='TRANSITION TABLES***STATE' $('A' T).' FOLLOWED BY LIST OF $('B' T)' FOR SUCCESSIVE INPUTS' SYSPOT =' I ='1' T J1 J ='1'= NULL'Al I'.' J'.0') 4 ~.E(QJ, N) /S( TEST'I) j = j + tl' / (NULL) -TESTI.EQ(I,N) /S($('TABLES' T)) I = I +'1' /(Jl) TABLESE TRIM(SYSPIT) *S*'/' *Z*',' *L* 6 SYSPOT ='' S'/' Z'' L $('FZ' S) = Z /(I1) TABLESY TRIM(SYSPIT) *S*',' *L* SYSPOT = S'' L I ='1' NEXTF1 $('FY' S'.' I) =.EQ(I,Q) /S(I1) f iI =I + 1' /(NEXTF),a l l ~~~~~~~I ='1'. ______....L L',' /($('L' T)) 1( —-.- LE L *J*',' = /(ADDA) LY L *J*'/' *Z*,' = __________l~~ ~$('FY' S'.' Z) = $('FY' S'.' Z)'U' I..'t_____ ADDA $('A' S'.' J'.O') = $('A' S'.' J'.O')'U' I.EQ(IP) /S(CL EAN) __ ___4_ _ _ I = I +'1' /($('L' T)) CLEAN =' EMPCK EQUALS($('A' S'.' J'.0'),) /S(EMP) $('A' S'.' J'.0')'U' =.EQ(SIZE($('A' S'.' J'.O')),'1') /S(SING) X ='S' /(ETEST) SING X ='1' ETEST.EQ(SJ) /F(FIN) X = X'E" FIN $('A' S'' J'.0') = X',' $('A' S'.' J'.0') /(CKJ) EMP.EQ(S,J) /S(L) ________ _ ~ $('A' S'.' J'.0') ='PL,' /(CKJ) L $('A' S'.' J'.0') ='L,' CKJ.EQ(J,N) /S($('OUT' T)) J = J +'1' /(EMPCK) OUTY J ='1' EMPCK1 EQUALS($('FY' S'.' J),) /S(EMP1) $('FY' S'.' J)'U' =.EQ(SIZE($('FY' S'.' J)),1t') /S(SING1) S('FY' S'.-' J) ='S,' $('FY' S'.' J) /(CKJ1) SING1 $('FY' S'.' J) ='1,' $('FY' S'.' J) /(CKJ1) EMP1 $('FY' S'.' J) ='PL,' -CKJ1.EQ(J,Q) /S(OUTE ) J = J +'1' /(EMPCK1)...

46 16, -— CUTE.EQ(S,N) /F($('TABLES' T)) K ='1' X ='1' Y ='0' 12 I ='1' J2 J ='1' NEXTR $('A' I'.' J'.' X) = UNION($('A' I'.' J'.'. Y),PROD(PROD($('A' I'.' K'.' Y),STAR($('A' K K'.''.' Y))) $('A' K.'.' J'.' Y))) R = UNION($('A' I'.' J'.' V),PROD(S('A' I'.' 18~. K'.' Y), PROD(STAR $('A' K'.' K'.' Y)),$'A' K'.' J'.' Y)))).LE(SIZE($('A' I'.' J'.' X)),SIZE(R)) /S(NJ) ('A' I'.' J'.' X) = R NJ.EO (J,N) /S( I ) J = J +'1' /(NEXTR) KI.E( I,N) /S(KN) I = I +'1' /(J2),t9 KN.F (K,N) /S(INL) K = K +'1' YT= Y 20 Y= X t X = YT /(I2) 2_ _ — INL L = TPIM(SYSPIT)',' 22. NSZ L *S*'/' *Z*',' /F(NEWM) SYSPOT ='-MACHINE NAME =' NAME', INITIAL STATE =' S', ACCEPTING OUTPUT =' Z RE ='PL,' J'1' /($('RE' T)),Z,3 REE.EQ($('FZ' J),Z) /F(NEXTJ) RE = UNION(RE,S('A' S'.' J'.' X)) /(NEXTJ) REY RE = UNION(RE,PROO(($('A S'.' J'.' X),$('FYI. J'.' Z))) NEXTJ.EQ(J,N) /S(ROUT) J = J +'1' /($('REe T)) ROUT RE'PL,' ='EMPTY' /S(OUT) RE'L,' ='L' /S(OUT) RE *Z*'E,' *A* ='LU' A /S(OUT) RE'11*,' *A* = A'*' /S(OUT) RE *Z*'*,' *A*'(' A')*' /S(OUT) RE *Z*,' *A* = A 24 CUT SYSPOT' TITLE ='EQUIVALENT RE = NEXTL RE = TITLE RE TITLE ='.LE(SIZE(RE),' 130') /S(LASTL) RE *A/'130'* *RE* SYSPOT = A /(NEXTL) LASTL SYSPOT = RE /(NSZ) ST1 B = A B *X*'L,' ='L,' /S(ST8) B'E' ='I*' /S(ST8) B' I*' /S(ST8) B ANCHOR()'I,' *X* /S(ST2) B'I' ='I*' /S(STB) B *X*',' *Y* = X'I*,' Y /(ST8) ST2 B ='SI*,/E' ST3 X ANCHOR()'(' *(Y)*' )' = /F(ST6) X ANCHOR()'*' = Y ANCHOR().'LU' ='-.Y = Y'U' Si T4 Y *(Z)*'U' = /F(ST3) ST5 B'/' Z'/' ='1' B'E' = Z'/E' /(ST4) ST6 X *Z*'*' = /S(ST5) B'/' *Z*'/E' = Z ST7 B'/' ='U' /S(ST7) ST8 STAR = B /(RETURN)

47 PRI A *TA*'' *SA* B *TB*',' *SB* TAB = TA TB TAB'P' /S(PR 10 ) TAb IL' = /S(PRl1) EQUALS(SASB) /F(PR13) TAB'* *X*'I' /S(PR14) TAb'*1 *X*'F' /F(PR2) PR1'4 C = A /(PR12) PR2 (TB TA)'*' *X*'II /S(PR15) (TB TA)'*' *X*'E' /F(PR13) PRl5 C = B /(PR12) PR3 X ='A' PR4 Y = ('T' X) Y'E' /F(PR5) (' S' X) ='(LU' $('S' X)') /(PR7) PR5 Y'S' /S(PR6) Y ANCHOR()' I*' /F(PR7) -O __PR6 $('S' X) ='(' $('S' X)')' O~......PR7 $('T' X)'E' ='I' Qc --. _. Y'*' /F(PR8) S('S' X) = $('S' X)'*' PR8 X'A' ='B' /S(PR4) (TA TB)' I' *X*'I' /S(PR9) C ='e' SA SB /(PR12) PR9 C =' I,' SA SB /(PR12) PR10 C ='PL,' /(PR12) P l11 C = TAB',' SA SB Pi 2 PROD = C / ( RETURN) PP13 TAB'*' *X*'*' /F(PR3) C = UNION(A,B) EQUALS(AC) /S(PR12) EQUALS (B,C) /S( PR12)F PR3) UNi A'PL' /S(UN12) B'PL' /S(UN13) A *TA*',' *SA* B *TB*',' *SB* TAB = TA TB TAB'L' /S(UN21) TAB'*6 *X*'*' /S(UN14) TA'*' /S(UN15) TB'*' /S(UN16) EQUALS(SA, SB) /S(UN22) UN2 X ='A' UN3 $('T' X)'*' /F(UN6) $('T' X)'1' /S(UN4) $('Y' X) =',(' $('S' X)')*,' i(UN5) UN4 $('Y' X) =',' $('S' X)'*,' UN5 X'A' ='B' /S(UN3)F(UN8) UN6 $('S' X) = $('S' X)'U' $('Y' X) =',' UN7 $('S' X) *(Z)*'U' = /F(UN5) $('Y' X) = $('Y' X) Z',' /(UN7) UN8 C = UN9 YA',' *Z*',' =',' /F(UNIO) YB',' Z',' /S(UN9) C = C',' Z /(UN9). UN10 C = C YB'E' C',' *Z*',F' = Z ~ ~ -'UN~l C',' ='U' /S(UNl1) TAB'I' /S(UN23) 3~ - TAB'E' /S(UN24) -N12 __ —-------- -— C ='S,' C /(UN25) UN12 C = B /(UN25) UN13 C = A /(.UN25) UN14.GE(SIZE(SA),SIZE(SB)) /F(UN16) UN15 YA ='A' YB ='B' /(UN17) UNI6 YA ='B' YB -'A' UN17.GE(SIZE($('S' YA)),SIZE($('S' YB))) /F(UN2) Z = *,' ZA = $('S' YA)'U' zB = $('S' YB)'U' UN18 ZA *(X)*'U' = /F(UN19) Z = Z X',' /(UN18) UNl9 ZB - *X* t'U' =. /F(UNF2O) Z',' X',' /SI UN19) F(UN2 )

48.' -" u 2,.? - c = s YA - /(UN25) -Zu L'~1 C = TAB', SA SB o IC.'l.' = C'L' /S(UN25) C'I' /S(UN25) C'E' /S(UN25) C *X*',' *Z* = X'E,' Z /(UN25) LN22 TA'I' /S(UN13) TH'1' /S(UN12) TA'E' /S( UN13)F(UN12) UN23 C ='SI,' C /(UN25) UN24 C ='SE,' C UN25 UNION = C /(RETURN) END _-..c~

V. Display the Lattice of SP Partitions A. Program SP name: B. Purpose: To display in a convenient manner the lattice of SP partitions for a specified finite-state machine. C. Method: For a given machine the set of two-state generators, S2, is formed as follows: S2 K min {7r7 I7 is an SP partition on S i, j e S such that 7 (i) = f (j)}; A, the set of lattice atoms, is A = min S2; B, the set of basic generators, is extracted from S2 and A via: B = A u {7rlirT S2 -A, a 7T'} i7' S, at < The lattice is then generated in successive rows, R(O), R(1),..., etc.... where R(O) = {zero partition} R(1) =A 49

50 ir e B- R'(k-1) or R(k) = min vT 7r = 7 + 7r2 for some 71 7T2' V 1' 2 ~ R' (k-l) such that 71 + c2 e R' (k-1) k-1 where R'(k-1) = E R(Q) f =0 R(m) = {the identity partition} The partitions are outputted row-by-row and are identified by number-zero designating the zero partition and the numbers 1,2,3,... etc. designating successively higher partitions in the lattice with the highest number belonging to the identity partition. As the partitions in each row are identified their identification number, row number, lattice type, immediate successor identification numbers and non-singleton partition blocks are listed. Finally, the two-state partitions induced by all state pairs are tabulated. D. Language and System: IBM System/360 FORTRAN IV to be run in the time-sharing mode on MTS (Michigan TermiAal System) as it existed at the University of Michigan, July 1967.

E. Operation: For on-line time-sharing execution run the object version of the program with 1 = *SOURCE* 2 = *SINK* All user input is supplied at program request in the following sequence: Program Types User Types 1) "MACHINE NAME? Any string of characters up to (TYPE UP TO 50 length 50 to identify the machine CHARACTERS)" about to be described. 2) "N? (TYPE A 3-DIGIT A single 3-digit integer corresNUMBER IN RANGE 1 ponding to N for the machine being TO 100)" described; 1 < N < 100; the number will be read by the format I3. If N is out of range the program will ask for N again. 3) "P? (TYPE A 1- DIGIT A single 1-digit integer corresponding NUMBER IN RANGE 1 to P for the machine being described; TO 5)" 1 < P < 5; the number will be read by the format IL. If P is out of range the program will ask for P again.

52 4) "STATE TRANSITION TABLE: FOR EACH I TYPE P 3-DIGIT NUMBERS SEPARATED BY COMMAS AND CORRESPONDING TO FS(I, J) FOR J=1 to P I = 1" P 3-digit integers separated by commas and corresponding to FS(1, 1), FS(1,2),..., FS(1, P); these numbers will be read by the format 5(3I, 1X). "I = 2" P 3-digit integers separated by commas and corresponding to FS(2, 1), FS(2,2),..., FS(2, P); these numbers will be read by the format 5(3I, 1X). "I = N" P 3-digit integers corresponding to FS(N, 1), FS(N,2),..., FS(N, P). 5) Re-capitulation of NAME, N, P and full TRANSITION TABLE information.

53 6) LATTICE TABLE in which each lattice point representing a partition with SP on the given machine is listed; each point is given an identification number; the row in the lattice of each point is indicated; the type for each point is specified according as the point is a lattice atom, a basic generator, a two-state generator or none of the above; the identification numbers of all points immediately less than each point are given; the nonsingleton blocks of each partition are enumerated (singleton blocks will be omitted from the output). 7) TWO-STATE GENERATOR TABLE in which is tabulated a list of the minimal SP partitions induced by each pair of states in the machine. The partition number refers to the

54 identification numbers listed in the LATTICE TABLE above. 8) "NEW MACHINE (O=NO, 1=YES)?" Zero or one as desired; number will be read by the format I1.

55 F. Sample Run #$RUN SPOBJ; 1 *SOURCE* 2:*SINK*. IBCOM# IS AN UNDEFI NED SYMBOL. #EXECUTION BEGINS SP LATTICE PROGRAM MACHINE NAME?(TYPE UP TO 50 CHARACTERS) HARTMANIS AND STEARNS,PAGE 42,MACHINE B N?(TYPE A 3-DIGIT NUMBER IN RANGE I TO 100) 008 P?(TYPE A 1-DIGIT NUMBER IN RANGE I TO 5) 2 STATE TRANSITION TABLE: FOR EACH I TYPE 2 3-DIGIT NUMBERS SEPARATED BY COMMAS AND CORRESPONDING TO FS(I,J) FOR J:l TO 2 I = 1 003,007 I: 2 004,008 I 3 001,006 I 4 002,005 I - 5 002,004 I: 6 001,003 I: 7 004,004 I: 8 003,003 SP LATTICE PROGRAM MACHINE NAME: HARTMANIS AND STEARNS,PAGE 42,MACHINE B N: 8 P 2

56 STATE TRANSITION TABLE I NP UTS STATE 1 2 1 3 7 2 4 8 3 1 6 4 2 5 5 2 4 6 1 3 7 4 4 8 3 3 LATTICE TABLE TYPE CODE: A=LATTICE ATOM B:BASIC GENERATOR 2=TWO-STATE GENERATOR NO. ROW TYPE 0 0 ZERO 1 1 AB2 SUCC: 0 BLOCK 1: 1 2 BLOCK 2: 3 4 BLOCK 3: 5 6 BLOCK 4: 7 8 2 1 AB2 SUCC: 0 BLOCK 3: 3 6 3 1 AB2 SUCC: 0 BLOCK 4: 4 5 4 2 B2 SUCC: I BLOCK 1: 1 2 3 4 BLOCK 2: 5 6 7 8 5 2 SUCC: 2 3 BLOCK 3: 3 6 BLOCK 4: 4 5 6 3 2 SUCC: 1 5 BLOCK 1: 1 2 BLOCK 2: 3 4 5 6 BLOCK 3: 7 8 7 4 2 SUCC: 4 6 BLOCK 1: 1 2 3 4 5 6 7 8

57 TWO-STATE GENERATOR TABLE STATE STATE PARTITION NO. 1 2 1 1 3 4 1 4 4 1 5 7 1 6 7 1 7 7 1 8 7 2 3 4 2 4 4 2 5 7 2 6 7 2 7 7 2 8 7 3 4 1 3 5 6 3 6 2 3 7 7 3 8 7 4 5 3 4 6 6 4 7 7 4 8 7 5 6 1 5 7 4 5 8 4 6 7 4 6 8 4 7 8 1 NEW' MACHINE(O=NO, I=YES)? MACHINE NAME?(TYPE UP TO 50 CHARACTERS) FARR,JOUR OF ACM,JULY 1963,PAGE 382,MACHINE B N?(TYPE A 3-DIGIT NUMBER IN RANGE I TO 100) 745 ***N OUT OF RANGE N?(TYPE A 3-DIGIT NUMBER IN RANGE I TO 100) 010 P?(TYPE A I-DIGIT NUMBER IN RANGE 1 TO 5) 7 ***P OUT OF RANGE P?(TYPE A I-DIGIT NUMBER IN RANGE I TO 5) 2

58 STATE TRANSITION TABLE: FOR EACH I TYPE 2 3-DIGIT NUMBERS SEPARATED BY COMMAS AND CORRESPONDING TO FS(I,J) FOR J:1 TO 2 001,006 I: 2 001,007 I: 3 001,007 I: 4 001,008 I: 5 002,008 I: 6 003,009 I 7 003,010 I - 8 004,010 I: 9 004,010 I = 10 005,010 SP LATTICE PROGRAM MACHINE NAME = FARR,JOUR OF ACM,JULY 1963,PAGE 382,MACINE B N- 10 P 2 STATE TRANSITION TABLE INPUTS STATE 1 2 1 1 6 2 1 7 3 1 7 4 1 8 5 2 8 6 3 9 7 3 10 8 4 10 g-. 4 10 10 5 10 -------------------------------— I~~~~ ~~~~~ ~ ~,'O~ ) -~(~,~~~

59 LATTICE TABLE TYPE CODE: A-LATTICE ATOM B=BASIC GENERATOR 2=TWO-STATE GENERATOR NO. ROW TYPE 0 0 ZERO I 1 AB2 SUCC: 0 BLOCK 1: 1 2 BLOCK 3: 4 5 BLOCK 4: 6 7 BLOCK 6: 9 10 2 1 AB2 S UCC: 0 BLOCK 2: 2 3 3 1 AB2 SUCC: 0 BLOCK 3: 3 4 BLOCK 6: 7 8 4 1 AB2 SUCC:- 0 BLOCK 8: 8 9 5 2 2 SUCC: 1 2 BLOCK 1: 1 2 3 BLOCK 2: 4 5 BLOCK 3: 6 7 BLOCK 5: 9 10 6 2 2 SUCC: 2 3 BLOCK 2: 2 3 4 BLOCK 5: 7 8 7 2 2 SUCC: 1 3 BLOCK 1: 1 2 BLOCK 2: 3 4 5 BLOCK 3: 6 7 8 BLOCK 4: 9 10 8 2 2 SUCC: 3 4 BLOCK 3: 3 4 BLOCK 6: 7 8 9 9 2 2 SUCC: 1 4 BLOCK 1: 1 2 BLOCK 3: 4 5 BLOCK 4: 6 7 BLOCK 5: 8 9 10

60 10 2 SUCC: 2 4 BLOCK 2: 2 3 BLOCK 7: 8 9 11 3 2 SUCC: 5 6 7 BLOCK 1: 1 2 3 4 5 BLOCK 2: 6 7 8 BLOCK 3: 9 10 12 3 B2 S UCC: 10 BLOCK 2: 2 3 BLOCK 4: 5 6 BLOCK 6: 8 9 13 3 2 SUCC: 7 8 9 BLOCK 1: 1 2 BLOCK 2: 3 4 5 BLOCK 3: 6 7 8 9 10 1 4 3 SUCC: 5 9 10 BLOCK 1: 1 2 3 BLOCK 2: 4 5 BLOCK 3: 6 7 BLOCK 4: 8 9 10 15 3 SUCC: 6 8 10 BLOCK 2: 2 3 4 BLOCK 5: 7 8 9 16 4 2 SUCC: 12 14 BLOCK 1: 1 2 3 BLOCK 2: 4 5 6 7 BLOCK 3: 8 9 10 17 4 SUCC: 11 13 1 4 15 BLOCK 1: 1 2 3 4 5 BLOCK 2: 6 7 8 9 10 18 4 S UCC: 12 15 BLOCK 2: 2 3 4 BLOCK 3: 5 6 BLOCK 4: 7 8 9 19 5 2 SUCC: 16 17 18 BLOCK 1: 1 2 3 4 5 6 7 g 9 10

TWO-STATE GENERATOR TABLE STATE STATE PARTITION NO. 1 2 1 1 3 5 1 4 11 1 5 11 1 6 19 1 7 19 1 8 19 1 9 19 1 10 19 2 3 2 2 4 6 2 5 11 2 6 19 2 7 19 2 8 19 2 9 19 2 10 19 3 4 3 3 5 7 3 6 19 3 7 19 3 8 19 3 9 19 3 10 19 4 5 1 4 6 16 4 7 16 4 8 19 4 9 19 4 10 19 5 -6 12 5 7 16 5 8 19 5 9 19 5 10 19 6 7 1 6 8 7 6 9 13 6 10 13 7 8 3 7 9 8 7 10 13 8 9 4 8 10 9 9 10 1 NEW MACHINE(O=NO, I=YES)? 0 IHC002I STOP 0 ***** RESTART AT LOCATION 0627D2 EXECUTION TERMINATED

G. Important Program Variables: EQUAL(N, PPM, TP1, PP, LEQ, PPEQ) is a subroutine which scans the partitions in the PP array comparing them with the partition in TP1; if a match is found then a return is made with LEQ = 1 and PPEQ = the address of the PP partition identical to the TP1 partition; if no match is found then a return is made with LEQ = 0; all partitions must be normalized and sized; rank, number and type codes are ignored. LEQ (See EQUAL) LESS (J, I, N, PP) is a logical function whose values is. TRUE. iff the partition with address J in PP is less than or equal to the partition with address L NORSIZ (N, TP1) is a subroutine which normalizes and sizes the partition given in TP1. PP is a linear array in which partition information is stored; each partition occupies a segment of length N+4 coded as follows:

63 Segment Cell Code rank: - 1 - old partition 0 - present partition > 1 - future partition 2 number: < 0 - temporary ID = 0 - zero partition > O - final ID 3 type: 1 - basic generator 2 - two-state generator 3 - none of the above 4 size: the number of blocks in the indicated partition 5, 6,..., N+4 correspond to the N states of the machine; two cells contain the same number iff their corresponding states are in the same block of the partition being described; when in normal form cell 5, the cell corresponding to state 1, will contain the number'1'; the cell corresponding to the least state not in the same block as state 1 will contain'2', etc..... The address of the segment corresponds to the N+4 cell.

64 PPEQ (See EQUAL) PPM = the index of the last cell of the last partition in the PP array REDUCE(N, P, FS, TP1) is a subroutine which replaces the partition in TP1 with the smallest partition with SP that contains it; the partition in TP1 need not be in normal form nor need it be ranked, numbered, typed or sized. S2 is a two-dimensional array; S2(I, J) is the number (either temporary or final) of the two-state generator partition obtained by equivalencing states I and J; if S2(I, J) = 0 then this partition is as yet unknown. SUM (N, TP1, TP2) is a subroutine which places the sum of the partitions in TP1 and TP2 into TP1; ranknumber, type and size are ignored; the initial and final partitions need not be in normal form. TP1 and TP2 are two linear arrays in each of which temporary information on a single partition may be stored; the format is the same as a single PP array segment.

65 Ho Annotated Flow Chart N, P, FS-TALE; PRINT NAME, N, P, FS-TABLE A IN PP ARAY r -PRESE'T PART rl eN S3 = 2 MIN FRUTU PAIr1iTI@NSj PRINT TrTLE, AND ROW E I - -- OF LATTICE MARK ALL PRESENrT PART(TleN AS eLD LeAD PE PARE' TITION INTe PP APP ALL NEW FPAR. 3UMS ARRAY", LABEL AS QF PRESENT PAiR"tTLINS eLD PAITr\eN;-; Te FIE PP ARRAY AS ZER2 e U- SZ, FUTUPRE PARTTrleNs ARRAY' - (g} R= R+d ADP ALL 2-STA'E, EENERATeRAS " NeT I PP ARPAY AS FUTURE r PARrTY A EN S SCAN PP ARRAY, NUMbE AND PP-IN PRrSF-.ET PATRTiTeNS ALONexN WS | R=1 i M | succE sseR. AND NelRt1; NP=O SI NGLE B LOC.K.. UP-DATE S2 ARRAy/ 6 C~CECKC IF PAIFl"TIGN SCAN 2 — STATE Q4ECK IF RA1ZEqTAE GENERATORS, LABEL EINC PJIEt is -e BASIC GE:N~EAT-RRS, LABEL LATThCE ATOMS AS PR.ESe 12 PARTIT-1 NS | PRINrT SZ ARRAA,PJ 3'NEW{ Lr8 A

66 I. Annotated Program Listing #$COPY SP TO *SINK* IMPLICIT INTEGER*2(A-Z) REAL*. TYPE LOGICAL LESS DIMENSION FS(100,5),NAME(50),PP(5000),S2(100,100) DIMENSION SUCC( 100),TPI(104),TP2(104),TYPE(4) DATA Q/'Q'/,TYPE/'AB2',' B2',' 2',''/_:FR-RST VARIABLE WRITE(2,10) G I.S A DUMMY 10 FORMAT(//ISHSP LATTICE PROGRAM) 20 WRITE(2,30) 30 FORMAT(//39HMACHINE NAME?(TYPE UP TO 50 CHARACTERS)) READ(1,40) NAME 40 FORMAT(50AI) 50 WRITE(2,60) 60 FORMAT(/43HN?(TYPE A 3-DIGIT NUMBER IN RANGE I TO 100)) READ(1,70) N 70 FORMPAT(I3) I F( * ( 101-N) )80,80, 100 80'JITE(2,90) SO FORMlAT(17H***N OUT OF RANGE) GO TO 50 100 W.ITE(2,110) 110 FORMAT(/41HP?(TYPE A I-DIGIT NUMBER IN RANGE I TO 5)) READ( 1, 120)P 120 FORMAT(I 1 ) I F(P* (6-P)) 130,130, 150 130 WRITE(2,140) 140 FORMAT(17H***P OUT OF RANGE) GO TO 100 150 WRITE(2,160) 160 FORMAT(//23HSTATE TRANSITION TABLE:) WRITE(2, 170)P 170 FORMAT(15HFOR EACH I TYPE,I2,16H 3-DIGIT NUMBERS) WRITE(2,171) 171 FORMAT(23HSEPARATED BY COMMAS AND) WRITE(2, 172) 172 FORMAT(24HCORRESPONDING TO FS(I,J)) WRITE(2, 180)P 180 FORMAT(IOHFOR J:l TO,I3) DO 200 I:1,N WRI TE(2, 190)I 190 FORMAT(/4HI =,I3) 200 READ(1,210)(FS(I,J),J1,P) 210 FORMAT(5(I3, 1X) ) WRITE(2,213) WRITE(2,10) WPITE(2,211) NAME 211 FORMAT(/15HMACHINE NAME:,50AI) WRITE(2,212) N,P 212 FORMAT(/4HN,13,5X,4HP:,I3) WRI TE(2,213) 213 FORMAT(/40(1H-)) WRI TE(2,214) 214 FORMAT(/22HSTATE TRANSITION TABLE) WRITE(2,220)(I,I=,P) 220 FORMAT(/1 IX,6HINPUTS/5HSTATE,3X,515) WRITE(2,221) 221 FORMAT(IH ) DO 230 I:1,N 230 WRITE(2,240)I,(FS(I,J),J:I,P) 240 FORMAT(I 4,4X, 515) WRITE(2,213) WRITE(2,250) 250 FORMA-T(/13HLATTICE TABLE) WRITE(2,251) 251 FORMAT(/25HTYPE CODE: A:LATTICE ATOM) WRITE(2,252) 252 FORMAT(IIX,17HB:BASIC GENERATOR) WRITE(2,253) 253 FORMAT(IIX,2 1 H2TWO-STATE GENERATOR) WRITE(2,260) 260 FORMAT(/14HNO. ROW TYPE) WRITE(2,270) 270 FORMAT(/14H 0 0 ZERO)

67 271 PP(1)-l PP(2) =0 PP(3) =3 PP(4) =N N3 N+3 N4-N+4 PPM-N4 PN- 1 DO 280 I1,N PP ( I+4) =I DO 280 J I,N 280 S2(I,J)=O DO 400 II1,N DO 400 J-I,N IF(I.EQ.J) GO TO 400 DO 290 K-I,N 290 TPI(K+4):K TP1 (J+4):I DO 370 K-1,P I F(FS (I,K )-FS (J,K ) ) 298,300,297 297 S2T:S2(FS(J,K ),FS (I,K )) GO TO 299 298 S2T:S2( FS (I,K ),FS (J,K ) ) 299 IF(S2T) 320,300,320 300 DO 310 M=I,N 310 TP2(M+4):M TP2 (FS (J,K)+4):FS (I,K ) GO TO 360 320 DO 340 M=2,PPM,N4 I F(PP(M)-S2T)3 40,330,3 40 330 MT:M-2 GO TO 350 340 CONTINUE 350 DO 355 M:5,N4 355 TP2 ( M)-PP (MT+M) 360 CALL SUM(N,TPI,TP2) 370 CONTINUE CALL REDUCE(N,P,FS,TP1 ) CALL NORSIZ(N,TPI) CALL EQUAL( N,PPM,TP1,PP,LEQ,PPEQ) I F(LEQ)390,390,380 3 8 0 S2 (I,J ) =PP (PPEQ-N-2) GO TO 400 390 DO 395 K:4,N4 395 PP(PPM+K) -TP1 (K) PP (PP01+3) =2 PP (PP M+2) =P N PP(PP+1l) -0 S2(I,J)=PN PN:PN-I PPM:PPM+N4 400 CONTINUE R-= NP:0=O N2:2*N+8 DO 470 I-N2,PPM,N4 DO 405 J-I,N 405 TP1 (J+4) =J S =O DO 430 J-N2,PPM,N4 IF(J.EQ.I.OR.PP(I-N).GE.PP(J-N)) GO TO 430 IF(.NOT.(LESS(J,I,N,PP))) GO TO 430 S=l JTJ -N4 DO 420 K=5,N4 420 TP2(K) =PP(JT+K) CALL SUM(N,TPI,TP2) 430 CONTINUE I F(S ) 440,450,440 440 CALL NORSIZ(N,TPI ) PP(I-N-3)=-I IF(TP1 (4)-PP(I-N))450,470,450 450 PP(I-N-I)-l 470 CONTINUE

68 471 DO 641 I1 I,PPM,N4 IF(PP(I) )641,480,641 480 NP:NP+I S PP(I+1) DO 500 J-1,N DO 500 K:J,N IF(S2(J,K )-S)500,490,500 490 S2(J,K):NP 500 CONTINUE PP(I+1 )=NP IT:I+N3 S=O DO 510 J:1,PPM,N4 IF(PP(J).NE.1) GO TO 510 J T=J+N3 IF(.NOT.LESS(JT,IT,N,PP)) GO TO 510 PP(J) =2 510 CONTINUE DO 530 J=I,PPM,N4 IF(PP(J).NE.2) GO TO 530 J T =J +N3 DO 520 K:1,PPM,N4 IF(PP(K).NE.2.0R.K.EQ.J) GO TO 520 KT:K+N3 IF(LESS(JT,KT,N,PP)) GO TO 525 520 CONTINUE S =S+1 SUCC(S):PP(J+1) GO TO 530 525 PP(J)=I 530 CONTINUE DO 535 J=I,PPM,N4 IF(PP(J).EQ.2) PP(J):I 535 CO NTI NUE IF(R-1 )550,540,550 540 T=l GO TO 600 550 IF(PP(I+2)-1 )570,560,570 560 T:2 GO TO 600 570 IF(PP(I+2)-2)590,580,590 580 T=3 GO TO 600 590 T=4 600 WRITE(2,601)NP,R,TYPE(T),(SUCC(J),J 1,S) 601 FORMAT(/I3,I5,2X,A3,3X,5HSUCC:,IOI4,(/21X,1OI4)) 610 JP=PP(I+3) DO 640 J:1,JP S=O DO 630 K:,N I F(PP(I+3+K)-J )630,620,630 620 S:S+I SUCC(S) =K 630 CONTINUE I F(S- 1) 640,640,63 5 635 WRITE(2,636)J,(SUCC(K),K =,S) 636 FORMAT(/I8X,6HBLOCK,I3,1H:, 1014,(/28X, 1014)) 640 CONTINUE IF(PP(I+3).EQ.1) GO TO 840 641 CONTINUE 642 R=R+1 DO 760 I=I,PPM,N4 IF(PP(I ))760,700,760 700 IT=I+N3 DO 759 J:I,PPM,N4 IF(I.EQ.J.OR.PP(J).NE.O) GO TO 759 DO 720 K:4,N3 TP1 (K+I)=PP(I+K) 720 TP2(K+1) =PP(J+K) CALL SUM(N,TPI,TP2) CALL NORSIZ(N,TPI) CALL EQUAL(N,PPM,TP1,PP,LEQ,PPEQ) IF(LEQ)759,740,759 740 DO 750 K=4,N4 750 PP(PPM+K) =TPI (K) PP(PPM+I )=-1 PP (PPM+2) = PN P N P N -1 PP ( PPM+3 ) =3 PPM=PPM+N4 759 CONTINUE 760 CONTINUE

69 DO 761 I:1,PPM,N4 10 IF(PP(I).EQ.O) PP(I)=I 761 CONTINUE DO 830 I:N4,PPM,N4 IF(PP(I-N3).EQ.1) GO TO 830 DO 810 J=N4,PPM,N4 IF(PP(J-N3).EQ.1.OR.I.EQ.J) GO TO 810 IF(LESS(J,I,N,PP)) GO TO 830 810 CONTINUE PP(I-N3)=O 830 CONTINUE GO TO 471 840 WRITE(2,213) WRITE(2,841) 841 FORMAT(/25HTWO-STATE GENERATOR TABLE) WRITE(2,842) 842 FORMAT(/5X,25HSTATE STATE PARTITION NO.,/IH ) DO 850 I:ltN DO 850 J=I,N IF(I.EQ.J) GO TO 850 WRITE(2,851 )I,J,S2(I,J),.850 CONTINUE 851 FORMAT(3X,3I6) WRITE(2,213) WRITE(2,852) t....j 852 FORMA T ( /25HNEW MACHINE(O=NO, I=YES)?) 14 - - EAD(1,120)N'"-15 -, IF(N)20,860,20 860 STOP END SUBROUTINE REDUCE (N,P,FS,TPI) IMPLICIT INTEGER*2(A-Z) DIMENSION FS ( 100,5),TPI(104) 1 N4=N+4 9 CONTINUE 10 DO 40 I=1,N DO 40 J=I,N IF(TPI(I+4).NE.TPI(J+4)) GO TO 40 DO 30 K=I,P l IF(TPI(FS(I,K)+4).EQ.TP1(FS(J,K)+4)) GO TO 30 ti A =TPI(FS (I,K)+4) B=-TPI (FS(J,K)+4) DO 20 M=5,N4 I F(TPI (M).EQ.B) TPI (M)=A 20 CONTINUE GO TO 9 30 CONTINUE 40 CONTINUE 50 R ETUR N END SUBROUTINE NORSIZ (N,TP1) IMPLICIT INTEGER*2(A-Z) DIMENSION TP1 ( 104) N4=N+4 DO 10 I-5,N4 10 TP (I )=-TP1 (I) I-1 DO 30 J-5,N4 rO IF(TP1(J)) 15,15,30 15 A-TPI(J) DO 20 K:J,N4 IF(TPI(K).EQ.A) TPI(K):I Z 20 CONTINUE I =I+1 30 CONTINUE TPI (4)=I-1 RETURN _ r END

70 SUBROUTINE EQUAL (N,PPM,TP1,PP,LEQ,PPEQ) IMPLICIT INTEGER*2(A-Z) DIMENSION TP1(104),PP(5000) N4:N+4 DO 20 I-N4,PPM,N4 DO 10 J-4,N4 IF(TPI(J).NE.PP(I-N-4+J)) GO TO 20 4d< CONTINUE LEQ - PPEQ-I GO TO 30 20 CONTINUE LEQ =O 30 RETURN END SUBROUTINE SUM (N,TP,TP2) IMPLICIT I NTEGER*2(A-Z ) DIMENSION TP1 (104),TP2(104) N4:N+4 DO 40 I-5,N4 IF(TP2(I).EQ.O) GO TO 40 A TP2 (I ) DO 30 J-I,N4 IF(TP2(J).NE.A) GO TO 30 IF(TPI(I).EQ.TPI(J)) GO TO 20 E-TPI(I) C-TP1(J) DO 10 K=5,N4 IF(TPI(K).EQ.C) TPI(K):B 10 CONTINUE 20 TP2(J):O 30 CONTINUE 40 CONTINUE R ETUR N END LOGICAL FUNCTION LESS(J,I,N,PP) I MPLICI T I NTEGER*2(A-Z) DIMENSION PP(5000) IT:I -N J T -J - N JT:J -N DO 10 K=I,N DO 10 MK,N u0 IF(PP(JT+K).EQ.PP(JT+M).AND.PP(IT+K).NE.PP(IT+M)) GO TO 20 10 CONTINUE LESS:.TRUE. R ETUR N 20 LESS-.FALSE. R ETURN END

VI. Bibliography General reference on finite-state machines and in particular on state diagnosing: [1] Gill, A., Introduction to the Theory of Finite-State Machines, McGraw-Hill, New York (1962). Regular Expresssions: [2] McNaughton, R. and Yamada, H., Regular Expressions and State Graphs for Automata, IRE Transactions on Electronic Computers, vol. EC-9, no. 1 (March 1960), ppo 39-47. [3] Harrison, M. A., Introduction to Switching and Automata Theory, McGraw-Hill, New York (1965). [4] Brzozowski, J. A., and McCluskey, Signal Flow Graph Techniques for Sequential Circuit State Diagrams, IEEE Transactions on Electronic Computers, vol. EC-12, no. 2 (April 1963), pp. 67-76. SP Lattices: [5] Hartmanis, J. and Stearns, R. E., Algebraic Structure Theory of Sequential Machines, Prentice Hall, New Jersey (1966). References to computer programs dealing with finite state machines: [6] Farr, E. H., Lattice Properties of Sequential Machines, Journal of the Association for Computing Machinery, July 1963, vol., no. 3, p. 365. This paper mentions a program to produce all the partitions with S. P. for a given machine for which N < 38, P < 40. 71

72 [7] Griffiths, T. V., M-460 Program Notes: Some LISP Routines for Manipulating Automata, AFCRL-66-84, February 1967, Physical and Mathematical Sciences Research Papers, no. 192, Data Sciences Laboratory Project 4641, Air Force Cambridge Research Laboratories, L. G. Hanscom Field, Bedford, Massachusetts. This paper details a number of LISP programs to represent machines, cascade them, minimize them, complement them, compute their behavioral union, intersection, star, and reverse, etc. [8] Roberts, M. B., A Generalized Recognizer for Finite State Languages, Moore School of Electrical Engineering, University of Pennsylvania Report no. 66-03, August 1965. This report discusses an IPL-V program to determine if a given symbol string is denoted by a given regular expression; programs to convert a regular expression to a state table and minimize it are also mentioned. [9] Silverstein, M., Computer Procedures for Analysis of Finite Automata, term project, University of California, Berkeley (1962). This paper mentioned IPL-V routines to minimize a given machine, develop distinguishing sequences for state pairs, determine multiple preset diagnosing and regular preset homing experiments (neither of these necessarily minimal).

[10] Sarma, Hota S., Design of a Computer Program for Minimization and State Identification of Automata, Masters thesis, Electrical Engineering, Tuskegee Institute, May 1966. This thesis describes a program written for online use of an IBM 1620 and which minimizes a given machine and determines minimal simple preset homing and diagnosing experiments for a given admissible set. [11] Sacco, W. J., A Computer Technique Useful for Some Problems in the Partitioning Theory of Sequential Machines, Memorandum Report no. 1733, March 1966, Ballistic Research Laboratories, U. S. Army Material Command, Aberdeen Proving Ground, Maryland. This paper gives no computer program but rather a technique for determining if (1) a given partition has SP, (2) two given partitions constitute a partition pair, and (3) two set systems constitute a system pair. addition, W. D. Maurer uses a computer to assist in minimally decomposing group machines; a report on his work is to appear in a new journal, The Journal of Computer and Systems Science.

UNIVERSITY OF MICHIGAN 11111111113 1 1111111111111111111111106 3 9015 03695 2060