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

Acknowledgements o to the Ford Motor Company for making their timesharing computer facilities available for the development of these programs.

Table of Contents Section Page Io Introduction 1 II, Conventions 3 IIIo Machine Simulation 4 IVo Checking a Machine for Strong Connectedness 10 Vo Machine Minimization 17 VIL Displaying a Machine's Automorphism Group 25 VIIo Bibliography 35 iii

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 first of two, describes the programs treating problems one through four, a second report treating problems

five through seven will follow. 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 four programs contained in this report are written in the BASIC language for use in a time-sharing environment. A conscious effort has been exerted to make them straightforward and easy to use.

II Conventions We will deal with N, P, Q Mealy machines where N = the number of states in state set S, 1 < N < 100 P = the number of symbols in input alphabet Al, 1 < P < 59 except for the machine minimization program Nh ere 1 < P < 3. Q = the number of symbols in output alphabet A03 We will only consider machines coded such that S = {1,2,,)N} AI {1 290 9P} A = any set of Q distinct integers. A machine is a system M =(S, AIT Ag FS, FZ> where S, AI A are as above and where FS, the next state function, maps S xAI -'S and FZ, the output function, maps S x AI - AO0 It is assumed that the user is familiar with the necessary theoretical concepts of finite state machine theory [See 1 and 2] and with the BASIC language and its operation. The programs are written to run under BASIC, Ford Motor Company Time Sharing System, Dearborn, Michigan, as it existed April 1967o *Moore machines can be handled by the artifice of defining an equivalent Mealy machine in which FZ is independent of the input.

III. Machine Simulation Ao Program Name: SIM Bo Purpose: To simulate the input/output behavior of any specified machine with initial state. An option is available to suppress or not suppress the typing of current state information (in order to demonstrate state identification experiments, for example, one may wish to suppress the current state information). C. Method: Given current state S1 and input I, the output is FZ(S1, I) and the new current state is FS(S1, I). Do Operation: All user input is supplied at program request in the following sequence~ Program Types User Types 1) "N, P?'" Two integers separated by a comma and followed by a RETURN and corresponding to N and P for the machine to be simulated; 1 < N < 100; 1 < P < 5o If N or P is out of range, the program will ask for N, P again.

2) After typing two lines After each "I?" type five of labels for the FS- integers separated by commas table, the program and followed by RETURN. will type N lines of The first P integers corresthe following form~ pond to FS(I, 1), FS(I, 2),.,?"I?" FS(I, P); the remaining integers are ignored but must be typed. They may be given any values and. are needed only to satisfy the inflexible format requirements of BASIC. 3) After typing two labels After each "I?" type five infor the FZ-table, the tegers separated by commas program will type N and followed by a RETURN. lines of the following The first P integers corresform, "I?"' pond to FZ(I, 1), FZ(I9 2),. ~ FZ(I, P); the remaining integers are ignored (See 2 above) 4) Program types full machine table in N lines of form,. I, FS(I, 1), FZ(I, 1), FS(I, 2),o., FZ(I, N) 5) "INITIAL STATE?'" One integer, in range 1 to N, followed by RETURN, this specifies the initial state of

the machine. 6) "STATE SUPPRESS?" Zero or one followed by RETURN; indicates if current state should be typed by program or noto 7) After typing appropri- The user has two options' ate labels, the pro- a) type integer in range 1 gram is ready for a to P followed by RETURN, simulation run. in which event the integer is interpreted as a legitimate machine input-the program responds by typing the output and next state (if not suppressed); the user can then type the next input and so on. b) type integer out of range 1 to P followed by RETURN in which event the program notes the illegal input and requests further instruction via a second integer and RETURN. With this second integer the user can indicate that he quits, wants to input to the current machine, wants to reset the state of current machine, or start defining a new machine.

E. Flow Chart CHECK1IEIR RAa&ES IlMPUf FS-TABLE SINPU F-'TABLE PRINT MACAINE LABLES IMPUT Si( NmrIAL STXT OMPUS X (sE SWI\TC-) I.E PRIN6 S I -INPUT I (E-r IP) T — Is I LE6ALI T- PRINT F(SI) D LET Si=FS(S,I)I, INPU3 y (s~ swnr~c) 3 -'''

F. Annotated Program Listing SIM 22: 13 TUES. —04/25/67 10 DIM F(100,5) 20 DIM G(100,5) 30 PRINPUT NP F(I,J)= FS(I,J) 40 INPUT NP 50 PRINT " " G(IJ)= FZ(I.J) 60 IF N*(IOI-N):.,O THEN 90 70 PRINT "N ILLEGAL" 80 GO TO 30 90 IF P*(6-P)3,O THEN 120 100 PRINT "P ILLEGAL" 110 GO TO 30 120 PRINT "FS-TABLE" 130 PRINT "STATE ENTRIES" 140 FOR I=l TO N 150 PRINT I, 160 INPUT F(I,I),F(I,2),F(I,3),F(I,4),F(II,5) 170 NEXT I 180 PRINT " 190 PRINT "FZ-TABLE" -200 PRINT "STATE ENTRIES" 210 FOR I=:1 TO N 220 PRINT I, 230 I NPUT G(I, ),G(I,2),G(I,3),G(I,4),G(I, 5) 240 NEXT I 250 PRINT " 260 PRINT"MACHINE TABLES FS,FZ" 270 PRINT" INPUTS" 280 PRINT"STATE " 290 FOR I:1 TO P 300 PRINT I" 310 NEXT I 320 PRINT" " 330 PRINT" " 340 FOR I=:1 TO N 350 PRINT I, 360 FOR J31 TO P 370 PRINT F(I,J);G(I,J); 380 NEXT J 390 PRINT" 400 NEXT I 410 PRINT " 420 PRINT "INITIAL STATE"; 430 INPUT S1 440 PRINT"STATE SUPRESS(O:NO, I=YES)" 450 INPUT X 460 PRINT " 470 PRINT"OUTPUT "; 480 IF X=: THENS10 490 PRINT"STATE " 500 GO TO 520 510 PRINT" " 520 PRINT"INPUT" 530 IF X:l THEN 560 540 PRINT" "S l 550 GO TO 570 560 PRINT" 4 " n.570 INPUT I, 5i 5 8.in..n,580 IF I*(P+1-I)>O THEN 650 6 590 PRINT"ILLEGAL INPUT(O:QUIT,1=NEW INPUT,2:NEW S1,3:NEW M)";,._..-600 —ltPJUT Y610 IFY:=3 THEN 30 ~[ 620 IF Y=2 THEN 420 630 IF Y=I THEN 530 8- _ 640 STOP 9 650 PRINT G(S1,I) 660 LET S1:F(Sl,I) i0' O j670 IF X=1 THEN 700 680 PRINT S1; 690 GO TO 570 700 PRINT" 710 GO TO 570 720 END

G. Sample Run SI M 22:07 TUES. —04/25/67 N,P?4,2 FS-TABLE STATE ENTRI ES 1?3,4,0,0,0 2 71,2,00,0 3?4,4,0,0,0 4?2,3,0,0,0 FZ -TABLE STATE ENTRI ES?70,1,0,0,0 2?1,1,0,0,0 3 70,0,0,0,0 4?1,0,0O0,0 MACHI NE TABLES FS,FZ INPUTS STATE 1 2 1 3 0 4 1 2 1 1 2 1 3 4 0 4 0 4 2 1 3 0 INITIAL STATE?1 STATE SUPRESS O-NO 1 YES]?0 OUTPUT STATE INPUT I?1 0 3?2 0 4?1 1 2?2 1 2?1 1 1 75 ILLEGAL INPUT[ OQUI T 1 NEW INPUT,2=NEW S 1,3NEW M]?1 1?2 1 4?-2 ILLEGAL INPUT O:QUI T,NEW INPUT,2NEW S3 t:NEW M?2 INITIAL STATE?1 STATE S UPR ESS( ONO, 1 Y ES 3] 71 OUTPUT I NP UT?1 O?2 O?1 1 72 1?1 1 72 1 76 ILLEGAL INPUT[ OQUIT, NEW INPUT,2:NEWS 1,3:NEW M]73 NtP?5,6 P ILLEGAL N,P?1 03,4 N ILLEGAL N,P?STOP RAN 35 SEC.

IV. Checking a Machine for Strong Connectedness A. Program Name: STR B. Purpose: To check if a specified machine is strongly connected. C. Method: Find G(1) the set of all states reachable from state 1 and H(1) the set of all states reaching state 1o M is strongly connected iff G(1) = H(1) = S. D. Operation: All user input is supplied at program request in the following sequence: Program Types User Types 1) "N, P?" Two integers separated by a comma and followed by a RETURN and corresponding to N and P for the machine to be checked; 1 < N < 100O 1 < P < 5. If Nor P is out of range the program will ask for N, P again, 2) After typing two labels After each "I?" type five infor the FS-table, the tegers separated by commas program will type N and followed by a RETURNo. lines of the following The first P integers corresform: "I?" pond to FS(I, 1), FS(I, 2),o o 9 FS(I, P); the remaining integers are ignored but must be typed. They may be given any

values and are needed only to satisfy the inflexible format requirements of BASIC. 3) The program will retype the machine table and the results of the analysis; if the machine is not strongly connected, an unconnected state pair will be displayed. 4) "NEW MACHINE(O=NO, Zero or one as desired, 1 YES)?" RETURN.

E. Flow Chart IFpo'I Ns P INP'i FS,-TABLE PJWT MACHI~E IABLE I|NP I (SET sW rW)4 ARE ALL STblES, FW4D STT'E I A STNTES F FIND I' ACCESS I LE i ACCESSI B LE FROM SATE 1? FROM SATE 1. PRINT'40of SiR0t4f6LY I7~ ~CONNECTED,CAJ4'T PPRJT "ALL S-r~rms REACH STAlE I AROM EsibFRDM SrA-E 1 FROM STAE 4. RS SIATE1F IFID 4STA'I ACCESSIBLE FROM wla^ FROM AL STATES| SAE 1 IS u l ACCESS \ILE. PRINT "14oT STRONLGL PRINT" MAC4IHE IS CONMECTEV,CAN'T |STRONG6LY COUNEED"I REACH STATE 4

F. Annotated Program Listing STR 21: 15 MON. —-04/24/67 10 DIM F(100,5) 20 DIM S(100) 30 DIM X(100) F(IL r 1 c -J) 40 PRINT"N,P"; 50 INPUT N,P 60 PRINT" " 70 IF N*(101-N)>O THEN 100 80 PRINT "N ILLEGAL" 90 GO TO 40 100 IF P*(6-P)>O THEN 130 110 PRINT "P ILLEGAL" 120 GO TO 40 130 PRINT "FS-TABLE" 140 PRINT "STATE ENTRIES" 150 FOR I-1 TO N 160 PRINT I, 170 INPUT F(I, 1),F(I,2),F(I,3) F(I,4)F(I,5) 180 NEXT I 190 PRINT" " 200 PRINT" n 210 PRINT"rtACHINE TABLE FS" 220 PRINT" INPUTS" 230 PRI NT"STATE "; 240 FOR I-1 TO P 250 PRINT I" n; 260 NEXT I 270 PRINT " 280 PRINT " 290 FOR I=1 TO N 300 PRINT I, 310 FOR J:1 TO P 320 PRINT F(IQ,J)" n 330 NEXT J 340 PRI NT " 350 NEXT 1 360 PRINT" 370 FOR I_1 TO N X(lI)i4 STATE I ACCESSIBLE 380 LET S(I):O 390 LET X(I)-O FROM STATE I 400 NEXT I 410 LET J-I 420 LET X(l) -l S(1t),S(2),...,S(J)- LIST OF STATES 430 LET S(1)=l 440 FOR I=1 TO N ACCESSIBLE FROM 450 IF S(I) =O THEN 820 ACCESSIBLE FROM 460 FOR K=- TO P STATE 470 LET L=F(S(I),}X) 480 IF X(L):1 THEN 520 490 LET X(L):1 500 LET J=J+l 510 LET S(J):L 520 NEXT K 530 NEXT I 3540 PRINT"ALL STATES ACCEqSIBLE FROM STATE 1."

14 550 FOR I:2 10 N 5560 LET S(I)2 N X(I)= 4 STATE I ACC-MIBLE 570 LET X(I)=O 580 NEXT I STA 59O —-LET- IJt 600 FOR I= TO NOF 610 IF S(I)-O THEN 760 S(1),S(2)..,S(J) LSST OF 620 FOR K=2 TO N STAES FROM 630 IF X(K) =1 THEN 720 4 640 FOR, L-1 TO P W1lCH STA E 1 650 LET M=F(KL) 660 IF M =S(I) THEN 690 IS ACCESSISLE 6'70 NEXT L 680 GO TO 720 690 LET X(M)=l 700 LET J=J+1 710 LET S(J)=M 720 NEXT K 730 NEXT I S 740 PRINT"MACHINE IS STRONGLY CONNECTED," 750 GO TO 870 760 FOR I=l TO N 770 IF X(I)=O THEN 790 780 NEXT I 790 PRINT "MACHINE NOT STRONGLY CONNECTED." 800 gOOPRINT "CANNOT REACH STATE I FROM STATE "I"." 810 GO TO 870 820 FOR I=I fO N 30 IF X(I):O THEN 850 840 NEXT I 850 PRINT"MACHINE NOT STRONGLY CONNECTED,",860 PRINT"CANNOT REACH STATE "I" FROM STATE I," 0 870 PRINT"NEW MACHINE(O=NO, 1=YES)" 880 INPUT I 9 --- 90 I IF =l THEN 40'o -.t... 900 STOP 910 END

G. Sample Run STR 21105 MON. —*04/24/67 N,P?4,2 FS -TABLE STATE ENTR I ES 1?3,4,0,0,0 2 71,2,0,0,0 3?4,4,0,0,0 4?2,3,0,0,0 MACHINE TABLE FS INPUTS STATE 1 2 1 3 4 2 1 2 3 4 4 4 2 3 ALL STATES ACCESSIBLE FROM STATE 1. MACHINE IS STRONGLY CONNECTED* NEW MACHINE( ONO,IYES ]? N,P?7,2 FS-TABLE STATE ENTR I ES 1 73,2,0,0,0 2?3,2,0,0,0 3?71,1,0.,0,0 4?6,7,0,0,0 5?4,5,0,0,0 6?7,7,0,0,0 7 75,6,0,0,0 MACHINE TABLE PS I NP UTS STATE 1 2 1 3 2 2 3 2 3 1 1 4 6 7 5 4 5, 6 7 7 7 5 6 MACHINE NOT STRONGLY CONNECTED. CANNOT REACH STATE 4 FROM STATE 1.* NEW MA CHINE[ 0:NO, 1:Y ES ]? 1

NP?7 1 FS- TABLE STATE ENTRI ES i?2,0,0,0,0 2?3,0,0,0,0 3?4,0,0,0,0 4?5,0,0,OO 5 76,0,0,0,0 7 77,0,0,0,0 MACHINE TABLE FS I NP UTS STATE 1 1 2 2 3 3 4 4 5 5 6 6 7 7 7 ALL STATES ACCESSIBLE FROM STATE 1. MACHI HNE NOT STRONGLY CONNECTED. CANNOT REACH STATE I FROM STATE 2 NEW MACHI NE[ ONO, =YES ]?1 N,P?7,9 P ILLEGAL N,P?397 5 N ILLEGAL N,P?STOP RAN 29 SEC.

V. Machine Minimization Ao Program Nameo MIN B. Purposeo To find and display the minimal form of a specified machine. Co Method, The k-equivalence method is used wherein for any k > 1, Pk is a partition on S such that for I, J e S I - J(Pk) iff I is k-equivalent to J. P1 is constructed from the FZ table according to I_ J(P1) iff (V X e AI)[FZ(I, X) = FZ(J, X)]. Pk is constructed from P-k-1 according to I= J(Pk) iff I J(Pkl ) and (V X e AI)[FS(I, X) FS(J, X)(Pkl)]O For some K < N Pi.1 = PK and the minimal form of M will have iPKj states. If IPKI = jS I M is minimal; if UPK| < ISi then the minimal form of M is obtained by associating its states with the equivalence classes of PK; Do Operation' All user input is supplied at program request in the following sequence' Program Types Machine Types 1) "N,P?" Two integers separated by a comma and followed by a RETURN and corresponding to 17

N and P for the machine to be minimized; 1 <N< 100; 1 < P < 3. If N or P is out of range, the program will ask for N, P again. 2) After typing two labels After each "I?" type three for the FS-table, the integers separated by commas program will type N of and followed by RETURN. The the following form: first P integers correspond "I?" to FS(I, 1), FS(I, 2), oo o FS(I, P); the remaining integers are ignored but must be typedo They may be given any values and are needed only to satisfy the inflexible format requirements of BASIC. 3) After typing two labels After each "I?" type three for the FZ table, the integers separated by commas program will type N and followed by a RETURN, lines of the following The first P integers corresform: "I?" pond to FZ(I, 1), FZ(I, 2),. 0 FZ(I, P); the remaining integers are ignored (see 2 above)o 4) Program types full machine table in N lines of form:

19 I, FS(I, 1), FZ(I, 1), FS(I, 2),..., FZ(I, N) 5) If the machine is minimal as given the program types "MACHINE MINIMAL AS GIVEN. "; if not, the equivalence classes of M are displayed and labelled and the full table of the minimal machine is displayed using the equivalence class labels as state nameso 6) "NEW MACHINE(O=NO, Zero or one as desired, 1 =YES)? " RETURN.

20 E. Flow Chart R(L,O) = PARTrrfIO BLCK CONTAINIG STATEI R(I,J)- PARTITION BLOCK 11X4r P NHP 9 CONTAIN146 FS'(I,J) CHECK114EIR RAN6ES INPUT FS-TABLE INPUi FE-TAbLE PRINT MACHINE TABLES.INTALIZE R(IO. I BY COMPARIN6 ROWS OF IE T FZ -TAB LE I SEr R(IJ) BY INPI(ET.,. __. —- -- PRINT TABLE FOR | COMF-PVE NEW RI,O)\l I MINIMAL MACHINE BY COMPARN1G ROWS OF R(I,J). SET St=t, IF NEW VALUES ARE LABEL AND PRINT DIFFERWENT 11A OLD EQUIVALENCE CLASSES _ O =4? OES SIZE OF FINAL PARTrIIOM EQUAL N? RIm-TI MAACHINE MIIMAI Ac, ll=' tl I

21 F. Annotated Program Listing MI N 22:33 MON. —-04/24/67 10 DIM F(100,3) 20 DIM G(100,3) 30 DIM R(100,3) -40 PRINT"NP"; F(IJ) FS (,j) 50 INPUT N,P 60 PRINT" " G(IJ) = FZ(IJ) 70 IF N*(IOI-N)"O THEN 100 80 PRINT "N ILLEGAL" C= NUMBER OF 90 GO TO 40 100 IF P*(4-P)vO THEN 130 BLOCKS 1I 110 PRINT "P ILLEGAL" PARTITION 120 GO TO 40 130 PRINT "FS-TABLE" 140 PRINT "STATE ENTRIES" 150 FOR I=:1 TO N 160 PRINT I, 170 INPUT F(I,1),F(I,2),F(I,3) 180 NEXT I 190 PRINT " 200 PRINT "FZ-TABLE" 210 PRINT "STATE ENTRI ES" 220 FOR I=1 TO N 230 PRINT I, 240 INPUT G(I, ),G(I,2),G(I,3) 250 NEXT I 260 PRINT " 270 PRINT"MCHINE TABLES FS,FZ" 280 PRINT" INPUTS" 290 PRI NT"STATE 300 FOR I:1 TO P 310 PRINT I" 320 NEXT I 330 PRI NT " 340 PRI NT " 350 FOR 1:l TO N 360 PRINT.I, 370 FOR J=l TO P 380 PRINT F(I,J);G(IJ); 390 NEXT J 400 PRINT" " 410 NEXT I 420 PRINT" " 430 FOR I=:1 TO N 440 LET R(I,O)=O 450 NEXT I 460 LET C:O 470 FOR I:1 TO N 480 IF R(I,O)<>O THEN 560 490 LET C:C+l 500 FOR J:I TO N 510 FOR K=1 TO P 520 IF G(I,K)<>G(JK) THEN 550 530 NEXT K 540 LET R(J.O)=C 550 NEXT J,560 NEXT I 570 FOR I=1 TO N 5 FOR J=1 TO- P 3 590 LET R(I9J):R(F(IJ)vO) 600 NEXT J.610 NEXT I

22 -'20'LET S 1=0 S30 FOR I-l TO N F(I,O )=1O ROW OF R(I,J)'S SAME W4o LET F(IO)=O 650 NEXT I AS SOME PRIORN ROW 660 FOR I=1 TO N 670 IF F(I,O)=l THEN 810'. ITS EFFECT ON 680 LET S=O 690 FOR J=I TO N PARTITION ALREAItY 700 IF R(I,O)-'R(J,O) THEN 790 COMPLTED 710 FOR K=l TO P COMPUTED 4 720 IF R(I,K)4"R(J,K) THEN 760 740 LET F(J,O)=l S(SwrrTC) =t1 4E PARrTION 750 GO TO 790 760. LET S=I BLOCK ADDED DUE'10 770 LET S1:- I- ROW OF R(I S 780 LET R(J,O)=C+l 790 NEXT J 800 LET C=C+S 810 NEXT I 5 _ 820 IF SI=l THEN 570 6z 3 _ $30 IF C=N THEN 1210 840 PRINT"EIIUIVALENCE CLASSES" 850 FOR I=1 TO N 860 LET F(I,O)=O - F(I,0)= BLOCK LABEL ON FINAL 880 LET K-O PARTITION CONTAINK6+ 890 FOR I=1 TO N 900 IF F(I,o)<co THEN 990 STATE I 910 LET K=K+l 920 PRINT K"***"; 930 FOR J =I TO N 940 IF R(J,O)<R(I[O) THEN 970 950 LET F(J,O)=K 960 PRINT J; 970 NEXT J 980 PRINT "" 990 NEXT I 1000 PRINT " 1010 PRINT"EQUIVALENT MCHINE TABLES FS,FZ" 1020 PRINT" INPUTS " 1030 PRINT"STATE "; 1040 FOR I=l TO P 1050 PRINT I" 1060 NEXT I 1070 PRINT " 1080 PRINT" " 1090 FOR I=l TO C 1100 PRINT I, 1110 FOR J=l TO N 1120 IF F(J,O)<>I THEN 1180 1130 FOR K=l TO P 1140 PRINT F(F(J,K),O);G(JK); 1150 NEXT K 1160 PRINT " 1170 GO TO 1190 1180 NEXT J 1190 NEXT I 1200 GO TO 1220 9 1210 PRINT"MACHINE MINIMAL AS GIVEN," 1 1220 PRINT " 1230 PRINT" 1240-PRI -NT- " NEW MACHI-NE(0 —N, t- Y-ES > J 1250 INPUT I...:1260 IF Ic<>O THEN 40 4~,~2.~S~t ii 1270 STOP 1280 END

23 G. Sample Run MI N 22:24 MON. —-04/24/67 N,P?9,3 FS-TABLE STATE ENTR I ES 1?2,2,5 2?1,4,4 3 72,2,5 4 73,2,2 5 76,4,3 6?8,9,6 7 76,2,8 8?4,4,7 9 77,9,7 FZ -TABLE STATE ENTR I ES 1 71,0,0 2?Ol,l 3?710,0 4?0,1,1 5 71,0,0 6?0,1,'1 7?710,0 8 71,0,0 9 70,1,1 MACHI NE TABLES FS, FZ INPUTS STATE 1 2 3 1 2 1 2 0 5 U 2 1 0 4 1 4 1 3 2 1 2 0 5 0 4 3 0 2 0 2 1 5 6 1 4 0 3 0 6 8 0 9 1 6 1 7 6 1 2 0 8 0 8 4 1 4 0 7 0 9 7 0 9 1 7 1 EQUIVALENCE CLASSES I *** 1 3 8 2 *** 2 4 3 *** 5 7 4 *** 6 5 *** 9 EQUIVALENT MACHINE TABLES FSFZ I NP UTS STATE 1 2 3 1 2 1 2 0 3 0 2 1 0 2 1 2 1 3 4 1 2 0 1 0 4 1 0 5 1 4 1 5 3 0 5 1 3 1 NEW MACHI NE[ 0 NO, 1:YES ]71

24 FS -TABLE STA TE ENTRI ES I 72,3,0 2?1,3,0 3?3,2,0 FZ -TABLE STATE ENTR I ES I 1,5,0 2?2,3,0 3?2,10,0 MACHINE TABLES FS,FZ INPUTS STATE 1 2 1 2 1 3 5 2 1 2 3 3 3 3 2 2 10 MACHINE MINIMAL AS GIVEN, NEW MACHINE[ ONO, 1 =YES ]?1 N,P?4,4 P ILLEGAL N,P?1,5 P ILLEGAL N,P?107,2 N ILLEGAL N,P?S TOP RAN 41 SEC.

VI. Displaying a Machine's Automorphism Group A. Program Nameo AUTO B. Purpose: To compute and display the state automorphisms and their group for a specified machine. We (1) will limit consideration to machines in which the full state set S is reachable from State, 1 and (2) due to format constraints will display the group table for the automorphisms only when N < 10. If N > 10 the user can construct the group table himself by examining the automorphisms directly. C. Method: If all states of M are reachable from state 1 then 1) there are at most N automorphisms of M 2) each corresponds to a permutation on S and 3) each can be generated from the single point mapping h(1) E S on state 1 and the recursion equation (V I e S, X ( AI)[h(FS(I, X))= FS(h(I), X)]. Conversely we can test if a mapping h(1) c S on state 1 generates an automorphism on M by applying the above recursion equation. One of three possibilities results: 1) a complete permutation is induced on S 2) a conflict occurs in using the recursion equation 25

26 thus indicating no automorphism exists for the assumed h(l,), or 3) a permutation is induced on a proper subset of S —indicating some states are not reachable from state 1. We will generate the full automorphism group by testing iff h(1) = k generates an automorphism for each 1 <k < N (i. e. k S). D. Operation: All user input is supplied at program request in the following sequence: Program Types User Types 1) "N, P?" Two integers separated by a comma and followed by a RE TURN and corresponding to N and P for the machine to be simulated; 1 < N < 100; 1 < P< 5. If N or P is out of range the program will ask for N, P again. 2) After typing two lines After each "I?" type five inteof labels for the FS- gers separated by commas table, the program and followed by RETURN. will type N lines of The first P integers corresthe following form~ pond to FS(I, 1), FS(I, 2), 0 0 "I?" FS(I, P); the remaining

27 integers are ignored but must be typed. They may be given any values and are needed only to satisfy the inflexible format of BASIC. 3) The program will retype the machine table and the results of the analysis. Every nontrivial automorphism will be displayed and if N < 10, the full group table will be typ edo 4) "NEW MACHINE(O=NO, Zero or one as desired, 1=YES)?" RETURN.

28 E. Flow Chart Sl'o INPU N, P I= CHIECK11EIR RANGES' 7 INPUT FS-TABLE PRINT MACHINE INPU'. (,E' swrTC~) TABLE~~~~~~~ | IP UT I (SET SW ITA TABLE - — f' - PRINT GRO1U PRINT:,<~'OU P I"A6- TABLE |01 IS 1HE IDENSTI TY EQUALT IDEC TIT CPITy CAPAC IcrY EXCEEDED SET C=i t4>4o; K=2 T F PRINT NO K_>N?L ~(C~11~~ NO 3WN-TRIVIAL'>N =i? T AUTM'OR tRSM,~ AR AL,T~ -- RE ALL STATES ACCESSIBLE FIND STATE I ACC., FROM STATE I? DOES NOT NOT ACCESSIBLE NO AUTO. STATE 1 -- STATE K FORCE ACC. FROM STATE 1. AN AUlOMORPHISM ON M? PRINT CAN'T REACH SITATE ACC.,ALO I 1 FROM STATE 1 PI, NT NEW ]. AvUOMORPHISM J- C=C+ + [-. —— 1 ~ - qC = UMBER OF SET H(ZC) tT N. NT. ArOMORP'ISMS EQUALTO NEW H(I, J)= IMAGE OF AUOMORPI ISM I F STATE A UNDER J-'l ALfOMORPHISM

29 F. Annotated Program Listing AUTO 22:38 TUES — 04/25/67 10 DIM F(100,5) 20 DIM G(100) 30 DIM H(10,10) 40 PRINT"N,P"; F(1,J)* FS(IJ) 50 INPUT NaP 60 PRINT" 70 IF N*(101-N):>O THEN 100 80 PRINT "N ILLEGAL" 90 GO TO 40 100 IF P*(6-P)xO THEN 130 110 PRINT "P ILLEGAL" 120 GO TO 40 130 PRINT "FS-TABLE" 140 PRINT "STATE ENTRIES" 150 FOR I=l TO N 160 PRINT I, 170 INPUT F(I,1I),F(I,2),F(I,3),F(I,4),F(I,5) 180 NEXT I 190 PRINT " 200 PRINT " 210 PRINT"MACHINE TABLE FS" 220 PRINT" INPUTS" 230 PRINT"STATE "; 240 FOR I=1 TO P 250 PRINT I "; 260 NEXT I 270 PRINT" " 280 PRINT " 290 FOR I=1 TO N 300 PRINT I, 310 FOR J:l TO P 320 PRINT F(I,J)" " 330 NEXT J 340 PRINT" " _ 350 NEXT I 360 PRINT" " 370 PRINT"AUTOMORPHISM NO.1 IS THE IDENTITY." 380 FOR I=:1 TO 10 3 390 LET H(I,1):I 400 NEXT I 4_L, 410 LET C=l 420 FOR K:2 TO N 430 FOR I=- TO N G(1)-= LtAGE OF STATE 1I UNDER 440 LET G(I)=O 450 LET F(I,O)=O AOTOMORPI\SM CURRENMLY 460 NEXT IDE LO I 470 LET G(I):K DEVELOPIN6 480 LET S=l 490 FOR I =S TO N H] =i EFF 500 IF G(I):O THEN 590 O S CCES[/ N 510 IF F(I,O)-<O THEN 590 OF I() v;\E)O a ON 520 LET F(IO)=l C Z DE LOI 530 FOR J=l TO P CUREt'TLY DEVELOPIN 540 IF G(F(I,J)):O THEN 570 AUTOM0R10l4SM AS 550 IF G(F(IJ)):F(G(I),J) THEN 580 560 GO TO 840 BEN No 58.....NEXT ZJ 5, 6 ~o 5G80T St:.:..- tJ)J s t' = 0 =' -SOME STATE 1Ot 600'LET'-= ACCESSIBLE FRoM S'TAE 1, 610 FOR I=1 TON FF OF )'S 620 IF F(I,O)<';O THEN 670 =4 = E FE OF G()L 630 IF G(I)=O THEN 660 SUCCESSORS WNOTD FOIR 640 LET S=I 650 GO TO 490 ALL t 660 LET S:O 680 IF S:O THEN 1110 i c 690 FOR I -2 TO N OU | r -v 700 IF G(I):I THEN 730 710 NEXT I 720 GO TO 840

30 7...i 7so LEgT C:C+i 740 IF N,1O ~I'EI4 7&0 750 FOR I=1 TO N 760 LET H(I-,C) G(I) 770 NEXf I 780 PRINT" " 790 PRINT"AUTOMORPHISM NO."C 800 PRINT " " tO 810 FOR I=l TO N 820 PRINT I;G(I) 830 NEXT I 5 — 840 NEXT K j4 850 PRINT " " 860 IF Cc<> THEN 890 870 PRINT"NO NON-TRIVIAL AUTOMORPHISM EXISTS." _ 880 GO TO 1150 890 PRINT "" 900 IF N>10 THEN 1090 910 PRINT"GROUP TABLE" 920 PRI NT" 930 PRINT" 940 FOR I:1 TO C 950 PRINT I; 960 NEXT I 970 PRINT" 980 FOR I= TO C 14 990 PPINT I; 1000 FOR J=l TO C 1010 FOR K=l TO C 1020 IF H(I,K)=H(H(1,I),J) THEN 1040 1030 NEXT K 1040 PRINT K; 1050 NEXT J 1060 PRINT " 1070 NEXT I 1080 GO TO 1150 1090 PRINT"NO GROUP TABLE —CAPACITY EXCEEDED.:" i ii,'1100 GO TO 1150 1110 FOR I=2 TO N 16 1120 IF G(I)=O THEN 1140 1130 NEXT I 1140 PRINT"CANNOT REACH STATE"I"FROM STATE 1." 1150 PRINT " 1160 PRINT"NEW MACHINE(O:NO,1:YES)"; 1170 INPUT I 48- 1180 IF Ic,0 THEN 40 19 i,. 1190 STOP 1200 END

31 G. Sample Run AUTO 22t23 TUES. —04/25/67 N,P?10,3 FS-TABLE STA TE ENTRI ES I?1,2,3,0,0 2?2,3,4,0,0 3 3, 4,,0,0 4?4,5,6,0,0 5 75,6,7,0,0 6?6,7,8,0,0 7 77,8,9,0,0 8?8,9,10,0,0 9?9,10,1,0,0 10?10,12,0,0 MACHI NE TABLE FS INPUTS STATE 1 2 3 I 1 2 3 2 2 3 4 3 3 4 5 4 4 5 6 5 5 6 7 6 6 7 8 7 7 8 9 8 8 9 10 9 9 10 1 10 10 1 2 AUTOMORPHISM NO, IS THE IDENTITY. AUTOMORPHISM NO. 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 AUTOMORPHISM NO. 3 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 1 AUTOMORPHISM NO, 4 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 1 9 2 10 3

32 AUTOMORPHISM NO. 5 1 S 2 6 3 7 4 8 5 9 6 10 7 1;8 2 9 3 10 4 AUTOMORPHISM NO. 6 1 6 2 7 3 8 4 9 5 10 6 1 7 2 8 3 9 4 10 5 AUTOMORPHISM NO. 7 1 7 2 8 3 9 4 10 5 1 6 2 7 3 8 4 9 5 10 6 AUTOMORPHISM NO. 8 1 8 2 9 3 10 4 1 5 2 6 3 7 4 8 5 9 6 10 7 AUTOMORPHISM NO. 9 1 9 2 10 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 AUTOMORPHISM NO, 10 1 10 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9

33 GROUP TABLE 1 2 3 4 5 6 7 8 9 10 I 1 2 3 4 5 6 7 8 9 10 2 2 3 4 5 6 7 8 9 10 1 3 3 4 5 6 7 8 9 10 1 2 4 4 5 6 7 8 9 10 1 2 3 5 5 6 7 8 9 10 1 2 3 4 6 6 7 8 9 10 1 2 3 4 5 7 7 8 9 10 1 2 3 4 5 6 8 8 9 10 1 2 3 4 5 6 7 9 9 10 1 2 3 4 5 6 7 8 10 10 1 2 3 4 5 6 7 8 9 NEW MV CHINEO =NO, I Y ES?1 N,P?3, 1 FS -TABLE STATE ENTRI ES I?2,0,0,0,0 2?2,0,0,0,0 3?3,0,0,0,0 MACHINE TABLE FS I NPUTS STATE 1 1 2 2 2 3 3 AUTOMORPHISM NO,1 IS THE IDENTITY. CANNOT REACH STATE 3 FROM STATE 1. NEW MACHI NE[ ONO, 1 Y ES? 1 N,P?3,2 FS-TABLE STATE ENTRI ES 1?3,2,0,0,0 2?3,2,0,0,0 3?2,3,0,0,0 MACHINE TABLE FS I NP UTS STATE 1 2 1 3 2 2 3 2 3 2 3 AUTOMORPHISM NO.I IS THE IDENTITY, NO NON-TRIVIAL AUTOMORPHISM EXISTS, NEW MACHI NE[ O=NO, 1 =YES 371 N,P?12,6 P ILLEGAL N,P?123,2 N. ILL.EGAL

34 N,P?12,2 FS -TAB LE STATE ENTR I ES I?8,2,0t,0 2?3,3,000,0 3?4,4,0,0,0 6?5,51,0,0,0 7?2,8,0,0,0 8?9,0,,0,0 10?l11,11,,00,O -I1?12,12.0,0,0 12?7,6,0,0,0 MACHI NE TABLE FS I NP UTS STATE 1 2 1.8 2 2 3 3 3 4 4 4 5 5 5 6 6 6 1 12 7 2 8 9 10 10 10 11 11 1 1 12 12 12 7 6 AUTOMORPHISM NO.I IS THE IDENTITY, AUTOMORPHISM NO. 2 1 7 2 8 3 9 4 10 5 11 6 12 7 1 8 2 9 3 10 4 11 5 12 6 NO. GROUP TABLE —CAPACITY EXCEEDED, NEW MACHI NE[O:NOt Y ES?O TIME: 53 SECS.

VII. Bibliography General reference on finite state machines and in particular on strong connectedness and machine minimization: [1] Gill, A., Introduction to the Theory of Finite-State Machines, McGraw-Hill, New York (1962) Automorphisms on automata: [2] Bayer, R., Automorphism Groups and Quotients of Strongly Connected Automata and Monadic Algebras, IEEE Conference Record of 1966 Seventh Annual Symposipm on Switching Theory, October 26-28, 1966. References to computer programs dealing with finite state machines: [3] Farr, E. H, Lattice Properties of Sequential Machines, Journal of the Association for Computing Machinery, July, 1963, vol. 10, no; 3, p. 365. This paper mentions a program to produce all the partitions with S. P. for a given machine for which N < 389 P < 40. [4] 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, etco 35

36 [5] Roberts, M. B., A Generalized Recognizer for Finite State Languages, Moore School of Electrical Engineering, University of Pennsylvania Report No. 66-033 August 1965. This report discusses an. IPL-V program to deter.mine 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. [6] Silverstein, Mo, 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). [7] 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,

[8] Sacco, W. J 9 A Computer Technique Useful for Some Problems in the Partitioning Theory of Sequential Machines, Memorandum Report No. 1733, March 1966, Ballistic Research Laboratories9 Uo SO 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. In addition, Wo D. Maurer:uses a computer to assit 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 I3901I 03695 2086