Trailing-Edge
-
PDP-10 Archives
-
decuslib20-01
-
decus/20-0020/fsmmin.eng
There are 2 other files named fsmmin.eng in the archive. Click here to see a list.
100' NAME--FSMMIN
110'
120' DESCRIPTION--DETERMINES THE CLASSES OF EQUIVALENT STATES
130' OF ANY SPECIFIED FINITE-STATE MEALY MACHINE; IN ADDITION A
140' MINIMAL EQUIVALENCE MACHINE IS COMPUTED USING THE EQUIVALENCE
150' CLASSES AS STATES.
160'
170' SOURCE--THOMAS F. PIATKOWSKI, THAYER SCHOOL OF ENGINEERING
180'
190' INSTRUCTIONS--THE PROGRAM RUNS IN THE CONVERSATIONAL MODE AND ALL
200' PARAMETERS ARE INPUT IN RESPONSE TO PROGRAM GENERATED QUESTIONS.
210' THE FOLLOWING CONVENTIONS APPLY:
220' A FSM IS A SYSTEM <S,X,Z,FS,FZ> WHERE
230' S = THE STATE SET=(1,2,...,N), 1<=N<=100
240' X = THE INPUT ALPHABET= (1,2,...,P), 1<=P<=5
250' Z = THE OUTPUT ALPHABET= ANY SET OF INTEGERS
260' FS, THE NEXT STATE FUNCTION, MAPS S*X INTO S AND FZ,
270' THE CURRENT OUTPUT FUNCTION, MAPS S*X INTO Z.
275'
280' FOR FURTHER DETAILS ON FINITE-STATE MACHINES SEE, FOR
290' EXAMPLE:GILL, INTRODUCTION TO THE THEORY OF FINITE-STATE
300' MACHINES, MCGRAW-HILL,1962.
310'
320'
330' * * * * * * * * * MAIN PROGRAM * * * * * * * * *
340'
350 DIM F(100,5),G(100,5),R(100,5)
360 PRINT"STATE MINIMIZATION OF A FINITE-STATE MACHINE"
370 PRINT
380 PRINT"N,P";
390 INPUT N,P
400 PRINT" "
410 IF N*(101-N)>0 THEN 440
420 PRINT "N ILLEGAL"
430 GO TO 360
440 IF P*(6-P)>0 THEN 470
450 PRINT "P ILLEGAL"
460 GO TO 360
470 PRINT "FS-TABLE"
480 PRINT" I FS(I,J) FOR J=1 TO";P
490 FOR I=1 TO N
500 PRINT I;
510 MAT INPUT V
520 IF NUM=P THEN 550
530 PRINT"INCORRECT NUMBER OF ENTRIES--PLEASE RE-TYPE"
540 GO TO 500
550 FOR K=1 TO P
560 LET F(I,K)=V(K)
570 NEXT K
580 NEXT I
590 PRINT" "
600 PRINT "FZ-TABLE"
610 PRINT" I FZ(I,J) FOR J=1 TO";P
620 FOR I=1 TO N
630 PRINT I;
640 MAT INPUT V
650 IF NUM=P THEN 680
660 PRINT"INCORRECT NUMBER OF ENTRIES--PLEASE RE-TYPE"
670 GO TO 630
680 FOR K=1 TO P
690 LET G(I,K)=V(K)
700 NEXT K
710 NEXT I
720 PRINT" "
730 PRINT"MACHINE TABLES FS,FZ"
740 PRINT" INPUTS"
750 PRINT "STATE";
760 FOR I=1 TO P
770 PRINT TAB(5+10*I);I;
780 NEXT I
790 PRINT" "
800 PRINT" "
810 FOR I=1 TO N
820 PRINT I,
830 FOR J=1 TO P
840 PRINT TAB(5+10*J);F(I,J);TAB(10+10*J);G(I,J);
850 NEXT J
860 PRINT" "
870 NEXT I
880 PRINT
890 FOR I=1 TO N
900 LET R(I,0)=0
910 NEXT I
920 LET C=0
930 FOR I=1 TO N
940 IF R(I,0)<>0 THEN 1020
950 LET C=C+1
960 FOR J=I TO N
970 FOR K=1 TO P
980 IF G(I,K)<>G(J,K) THEN 1010
990 NEXT K
1000 LET R(J,0)=C
1010 NEXT J
1020 NEXT I
1030 FOR I=1 TO N
1040 FOR J=1 TO P
1050 LET R(I,J)=R(F(I,J),0)
1060 NEXT J
1070 NEXT I
1080 LET S1=0
1090 FOR I=1 TO N
1100 LET F(I,0)=0
1110 NEXT I
1120 FOR I=1 TO N
1130 IF F(I,0)=1 THEN 1270
1140 LET S=0
1150 FOR J=I TO N
1160 IF R(I,0)<>R(J,0) THEN 1250
1170 FOR K=1 TO P
1180 IF R(I,K)<>R(J,K) THEN 1220
1190 NEXT K
1200 LET F(J,0)=1
1210 GO TO 1250
1220 LET S=1
1230 LET S1=1
1240 LET R(J,0)=C+1
1250 NEXT J
1260 LET C=C+S
1270 NEXT I
1280 IF S1=1 THEN 1030
1290 IF C=N THEN 1680
1300 PRINT"EQUIVALENCE CLASSES"
1310 FOR I=1 TO N
1320 LET F(I,0)=0
1330 NEXT I
1340 LET K=0
1350 FOR I=1 TO N
1360
1370 IF F(I,0)<>0 THEN 1460
1380 LET K=K+1
1390 PRINT K;" ***";
1400 FOR J=I TO N
1410 IF R(J,0)<>R(I,0) THEN 1440
1420 LET F(J,0)=K
1430 PRINT J;
1440 NEXT J
1450 PRINT" "
1460 NEXT I
1470 PRINT" "
1480 PRINT"EQUIVALENT MACHINE TABLES FS,FZ"
1490 PRINT" INPUTS"
1500 PRINT "STATE";
1510 FOR I=1 TO P
1520 PRINT TAB(5+10*I);I;
1530 NEXT I
1540 PRINT" "
1550 PRINT" "
1560 FOR I=1 TO C
1570 PRINT I,
1580 FOR J=1 TO N
1590 IF F(J,0)<>I THEN 1650
1600 FOR K=1 TO P
1610 PRINT TAB(5+10*K);F(F(J,K),0);TAB(10+10*K);G(J,K);
1620 NEXT K
1630 PRINT" "
1640 GO TO 1660
1650 NEXT J
1660 NEXT I
1670 GO TO 1690
1680 PRINT"MACHINE MINIMAL AS GIVEN."
1690 PRINT" "
1700 PRINT" "
1710 PRINT"NEW MACHINE";
1720 INPUT I$
1730 IF I$="YES" THEN 370
1740 STOP
1750 END