1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 3 ch 1: Automata Theory</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 3:
<CITE>Beyond Programming</CITE> 2/e Copyright (C) 1997 MIT
<H1>Automata Theory</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls3.jpg" ALT="cover photo">
<TD><TABLE>
<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR>University of California, Berkeley</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/v3ch01.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v3-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../v3ch0/v3ch0.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v3ch2/v3ch2.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-3">MIT
Press web page for <CITE>Computer Science Logo Style</CITE></A>
</TABLE></TABLE>
<HR><P>Program file for this chapter: <A HREF="fsm.lg"><CODE>fsm</CODE></A>
<P>As I explained in the preface to the first volume, one of my purposes in
writing this series of books has been to urge computer hobbyists away from
the view of computer expertise as the knowledge of obscure characteristics
of some particular computer--how to program it in machine language, what
magic numbers can be found where in its memory, how to overcome the copy
protection schemes on its disks, and so on. The trouble with this sort of
machine-specific expertise is that it becomes obsolete when your favorite
computer does. From my point of view, one of the virtues of Logo as a
programming language is that its high level data structures direct your
attention away from questions about what goes where in memory,
allowing you to focus instead on a more abstract description of your problem.
<P>Automata theory is a further step in abstracting your attention away from any
particular kind of computer or particular programming language. In automata
theory we consider a <EM>mathematical model</EM> of computing. Such a model
strips the computational machinery--the "programming language"--down to
the bare minimum, so that it's easy to manipulate these
theoretical machines
(there are several such models, for different purposes, as you'll soon see)
mathematically to prove things about their capabilities. For the most part,
these mathematical models are not used for practical programming problems.
Real programming languages are much more convenient to use. But the very
flexibility that makes real languages easier to use also makes them harder
to talk about in a formal way. The stripped-down theoretical machines are
designed to be examined mathematically.
<P>What's a mathematical model? You'll see one shortly, called a
"finite-state machine."
<P>The point of this study is that the mathematical models are, in some
important ways, <EM>equivalent</EM> to real computers and real programming
languages. What this means is that any problem that can be solved on a real
computer can be solved using these models, and vice versa. Anything we can
prove about the models sheds light on the real problems of computer
programming as well.
<P>The questions asked in automata theory include these: Are there any
problems that no computer can solve, no matter how much time and memory it
has? Is it possible to <EM>prove</EM> that a particular computer program
will actually solve a particular problem? If a computer can use two
different external storage devices (disks or tapes) at the same time,
does that extend the range of problems it can solve compared to a
machine with only one such device?
<P>There is also a larger question lurking in the background of automata
theory: Does the human mind solve problems in the same way that a
computer does? Are people subject to the same limitations as computers?
Automata theory does not actually answer this question, but the insights
of automata theory can be helpful in trying to work out an answer.
We'll have more to say about this in the chapter on artificial intelligence.
<P><H2>What is a Computation?</H2>
<P>What kinds of problems can we give to our abstract computers? In
automata theory we want to focus our attention on computation itself,
not on details of input and output devices. So we won't try creating
a mathematical model of a video game.
<P>We will play a game, though. In this game the computer has a rule in mind.
You type in strings of letters, using only the letters <CODE>A</CODE>, <CODE>B</CODE>, and
<CODE>C</CODE>. The computer tells you whether each string follows the rule or
not. Your job is to guess the rule. For example, suppose you have done
these experiments:
<P><TABLE><TR><TH align="left"><U>accepted</U>
<TH align="left"> <U>rejected</U>
<TR><TD><CODE>ABC</CODE><TD> <CODE>CBA</CODE>
<TR><TD><CODE>AAA</CODE><TD> <CODE>BBB</CODE>
<TR><TD><CODE>ABCABCABC</CODE><TD> <CODE>BCABCABC</CODE>
<TR><TD><CODE>A</CODE><TD> <CODE>BBBBBBB</CODE>
<TR><TD><CODE>ACCCCCCCCC</CODE><TD> <CODE>CAAAAAAAAA</CODE>
</TABLE>
<P>You might guess, from these examples, that the rule is
"The string must begin with <CODE>A</CODE>." Once you've made a guess you can
test it out by trying more examples.
<P>The program to play the game is called <CODE>game</CODE>. It takes one input,
a number from 1 to 10. I've provided ten different rules. Rules 1 to 3
should be pretty easy to guess; rules 8 to 10 should be nearly impossible.
(Don't feel too frustrated if you don't get them.)
<P>A string can be any length, including length zero (the empty string). Each
time you type a letter the program lets you know whether the string you've
typed so far obeys the rule. The program indicates whether the string is
accepted or rejected by displaying the word <CODE>accept</CODE> or <CODE>reject</CODE> on
the screen. In particular, as soon
as you start <CODE>game</CODE> the program will tell you whether or not the empty
string is accepted by this rule. If you type the string <CODE>ABC</CODE> you'll
really be testing three strings: <CODE>A</CODE>, <CODE>AB</CODE>, and <CODE>ABC</CODE>. You
should type one letter at a time to make sure the program has a chance to
respond to it before going on to the next letter. To start over again with
a different string, press the Return key.
<P>You should stop reading now and try the game. In the following paragraphs
I'm going to talk about some of the answers, so this is your last
chance. After you've figured out at least some of the rules, come
back to the book.
<P><H2>Finite-State Machines</H2>
<P>The point of studying this game is that we're going to look at a way to design
a special-purpose abstract computer that understands one particular
rule. We can then ask questions about how much information the computer
needs to handle the job.
<P>You've seen the word <EM>state</EM> before in connection with the Logo
turtle. Its state includes its position and its heading. So one turtle
state might be "position <CODE>[17 82]</CODE>, heading <CODE>90</CODE>." In principle,
the turtle has an <EM>infinite</EM> number of possible states, because its
position and heading don't have to be integers. Its position might be <CODE>
[14.142 14.142]</CODE>, for instance.
<P>Anything that holds information can be in different states. As another
example, an on-off light switch has two states. Some lamps have four states:
off, low, medium, and high. A computer, too, has a certain number of states.
The state of a computer includes all the information in its memory at some
particular time.
<P>A machine that has only a limited number of states, like the example of the
light switch, is called a <EM>finite-state machine.</EM> For almost all of
this chapter we'll be dealing with finite-state machines. You might think
that that imposes a very severe limit on the kinds of computations we can
do. But note that in the game I asked you to play, a rule can accept an
infinite number of possible strings and reject an infinite number of
others. The accepted or rejected strings can be of any length. (Some rules
restrict the length of a string, but others allow any length at all.) In
some sense, a finite-state machine can still perform infinitely varied
computations.
<P>Consider the third game as an example. The rule is "Accept
any string that starts with <CODE>AB</CODE>." Here is a picture of a finite-state
machine that implements that rule:
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v3ch1/fsm3.gif" ALT="figure: fsm3"></CENTER>
<P>Each numbered circle represents a state. This machine has three
states. The <CODE>start</CODE> arrow indicates that the machine starts out in state
1. State 3 is shown with a <EM>double</EM> circle to indicate that it is an
<EM>accepting</EM> state. In other words, when the machine is in state 3 the
screen says <CODE>accept</CODE>. The other two states are not
accepting states.
Every time you type a character the machine switches from one state to
another. The arrow from state 1 to state 2 has an <CODE>A</CODE> next to its
tail. This indicates that when the machine is in state 1, an input of <CODE>
A</CODE> switches it to state 2. (The arrow from state 3 to itself has the
three letters <CODE>ABC</CODE> at its tail. This is a shorthand notation for
three separate arrows with heads and tails in the same place, one for each
letter.)
<P>This picture is actually incomplete. For a full description of the machine
we have to indicate what happens on any input in any state. In other words,
each circle should have <EM>three</EM> arrows coming out from it, one each
for <CODE>A</CODE>, <CODE>B</CODE>, and <CODE>C</CODE>. I've chosen to adopt the convention that
every machine has an unmarked state called <CODE>reject</CODE>. Any missing arrow
goes to that state; once the machine is in the reject state it stays
there forever. Here, then, is the complete diagram of the machine for game
3:
<P><CENTER><IMG SRC="fsm3-reject.gif" ALT="figure: fsm3-reject"></CENTER>
<P>From now on I won't draw the <CODE>reject</CODE> state, but you should
remember that it's really part of the machine description. So this machine
requires four states, not three.
<P>If the first input letter isn't <CODE>A</CODE>, the machine goes to the <CODE>reject</CODE>
state. If the first letter is <CODE>A</CODE>, the machine goes to state 2. Then,
if the second letter is <CODE>B</CODE>, the machine ends up in state 3 and accepts
the string <CODE>AB</CODE>. This is the shortest acceptable string.
<P>Each of the three arrows from state 3 loops right back into state
3 itself. (Remember, although only one arrow appears in the picture,
it is labeled with three letters, so officially it represents three
arrows.) This means that once the machine is in state 3 it stays
there no matter what inputs it gets. Any string that starts <CODE>AB</CODE> is
acceptable.
<P>Here is a machine for game number 2:
<P><CENTER><IMG SRC="fsm2.gif" ALT="figure: fsm2"></CENTER>
<P>In this machine the <EM>start state</EM> is also an <EM>accepting
state.</EM> (Every machine has exactly one start state, but it may have any
number of accepting states.) This machine never gets into the <CODE>reject</CODE>
state. That doesn't mean it doesn't reject any strings; all odd-length
strings are rejected in state 2. But a rejected string can redeem itself by
adding another input character, so state 2 allows a return to the accepting
state 1.
<P>Here is a machine for game number 5. (Notice that I'm saying "a
machine" and not "the machine"; it is always possible to design
other machines that would follow the same rule.)
<P><CENTER><IMG SRC="fsm5.gif" ALT="figure: fsm5"></CENTER>
<P>You probably had more trouble discovering rule 5 than rule
2, and it takes longer to say the rule in English words. But the
<EM>machines</EM> for the two rules are almost identical. (Remember,
though, that the rule-5 machine really has a third state, the <CODE>reject</CODE>
state, which is not shown in the diagram.)
<P>Here are machines for rules 7 and 9. With these machines as hints,
can you figure out the rules? Go back to the <CODE>game</CODE> program to test
your hypotheses.
<P><CENTER><IMG SRC="fsm79.gif" ALT="figure: fsm79"></CENTER>
<P>You should also get some practice translating in the other direction, from
English rules to machine diagrams. Here are a couple to work on: Rule 4 is
"To be accepted a string must be composed of doubled letters (<CODE>AA</CODE>,
<CODE>BB</CODE>, and <CODE>CC</CODE>) strung together." Rule 8 is "To be accepted a
string must contain an even number of <CODE>A</CODE>s."
<P><H2>Nondeterministic Machines</H2>
<P>Here is rule 6: "To be accepted a string must begin with <CODE>A</CODE> and end
with <CODE>C</CODE>." Strings accepted by this rule include <CODE>AC</CODE> (the shortest
possible), <CODE>ABC</CODE>, <CODE>AACC</CODE>, <CODE>ACAC</CODE>, <CODE>ABCABC</CODE>, and so on.
Between the initial <CODE>A</CODE> and the final <CODE>C</CODE> an accepted string can
have any combination of <CODE>A</CODE>s, <CODE>B</CODE>s, and <CODE>C</CODE>s. It's natural to
think of the string as having three parts: a fixed beginning, a variable
middle, and a fixed end. The three parts of the input strings can be
represented conveniently with three states in the machine, like this:
<P><CENTER><IMG SRC="fsm6nd.gif" ALT="figure: fsm6nd"></CENTER>
<P>The machine starts in state 1. To be accepted a string must start
with <CODE>A</CODE>. Therefore, an <CODE>A</CODE> arrow leads from state 1 to state 2. Any
other input at state 1 leads to the <CODE>reject</CODE> state.
<P>Once the machine is in state 2 it is ready for the middle part of
the string. In this middle part any combination of letters is allowed.
Therefore, there are three arrows from state 2 to itself, one for
every possible letter.
<P>Finally, a <CODE>C</CODE> arrow leads from state 2 to state 3, signaling the end
of an acceptable string. A string must end with <CODE>C</CODE> to be accepted.
<P>There is a problem with this machine: There are <EM>two</EM> <CODE>C</CODE> arrows
leading out from state 2. One is a loop back into state 2; the other
goes on to state 3. This situation reflects the fact that <CODE>C</CODE> serves
two different functions in this rule: <CODE>C</CODE> is an optional part of the
middle section of the string, and it's also the required final input
in the string.
<P>A machine with two arrows from the same state for the same input is
called a <EM>nondeterministic</EM> machine. Here is how such a machine
could work: Whenever there are two choices for the machine's
current state and input, the machine clones itself. One of the copies
follows each arrow. From then on, if <EM>either</EM> machine is in an
accepting state the string is accepted.
<P>Nondeterministic finite-state machines are more complicated
than deterministic ones. Does the added complexity "buy" any added
power? In other words, can a nondeterministic machine solve problems
that a deterministic machine can't? It turns out that the answer
to this question is no. Deterministic machines are just as powerful
as nondeterministic ones. This is an important theorem in automata
theory. I'm not going to prove it formally in this book, but to illustrate
the theorem, here is a deterministic machine that carries out game
6:
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v3ch1/fsm6d.gif" ALT="figure: fsm6d"></CENTER>
<P>This machine is similar to the nondeterministic version. It has the
same number of states and some of the connections are identical.
State 3 is more complicated, though. Also, in this machine, it is
no longer the case that each state of the machine corresponds exactly
to one of three parts of the input string. Specifically, when the machine is
in state 3 the string may or may not be finished.
<P><H2>Representing Machines as Logo Lists</H2>
<P>The <CODE>game</CODE> program uses finite-state machines to represent the rules
by which it accepts or rejects strings. (The machines must be deterministic
for the program to work.) Logo programs can't read circles and arrows,
so a machine is represented as a list. What information is actually
contained in an FSM diagram? The diagram shows that there are a certain
number of states (the circles), that there are certain transitions from one
state to another (the arrows), that one particular state is the start state
(the start arrow), and that certain states are accepting ones (the double
circles). As in any programming project, I could have chosen many different
ways to represent that information in the program.
<P>In the particular representation I chose, the list form of a machine
has three members. The first member is the number of the start state.
The second member is a list of arrows; each arrow is itself a list,
as I'll explain in a moment. The third member of a machine list is
a list of the accepting states of the machine. For example, here
is the machine for game 3 again, in both forms:
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v3ch1/fsm3.gif" ALT="figure: fsm3"></CENTER>
<PRE>[1 [[1 A 2] [2 B 3] [3 ABC 3]] [3]]
</PRE>
<P>The number <CODE>1</CODE> is the start state; the list <CODE>[3]</CODE> is the
list of accepting states. (This machine happens to have only one accepting
state.) Everything else is the list of arrows. Each arrow is also a list
with three members: the initial state (the tail of the arrow), the input
letter or letters, and the final state (the head of the arrow). The first arrow in
this machine is
<P><PRE>[1 A 2]
</PRE>
<P>This is the arrow from state 1 to state 2 associated with
the input <CODE>A</CODE>.
<P>The list <CODE>[3 ABC 3]</CODE> in this machine represents three arrows, using
the same shorthand as in the circle-and-arrow diagrams. I could equally
well have represented these arrows separately:
<P><PRE>[1 [[1 A 2] [2 B 3] <U>[3 A 3] [3 B 3] [3 C 3]</U>] [3]]
</PRE>
<P>As in the circle-and-arrow diagrams, I haven't explicitly represented the
transitions to the <CODE>reject</CODE> state in these lists. The program is
written so that if it doesn't find a transition for the current state and
input in the list of transitions, it goes into state number −1, its
representation for the <CODE>reject</CODE> state.
<P>Here are some more machine lists:
<P><PRE>Game 2: [1 [[1 ABC 2] [2 ABC 1]] [1]]
Game 7: [1 [[1 AB 1] [1 C 2] [2 C 1]] [1]]
Game 9: [1 [[1 AB 1] [1 C 2] [2 A 3] [2 B 1] [3 A 1]] [1]]
</PRE>
<P>At this point you should stop and play with the program. Make up
your own rules. The procedure <CODE>fsm</CODE> takes a machine list as input
and accepts strings based on that machine. (<CODE>Game</CODE> uses <CODE>fsm</CODE>
with particular
machines as inputs.) Try out your new rules to make sure you've designed
the machines correctly. Then get a friend to play with your rules.
If both of you are reading this book together you can have a competition.
(It's easy to design rules that are impossible to guess because there
are too many details. If you have a competition you should limit
yourselves to three states per machine.)
<P>You might be interested in reading through the
<A HREF="v3ch1.html#fsm"><CODE>fsm</CODE></A> program, which
simulates a finite-state machine when given the machine's description
as its input. It's a pretty simple program. If you think of a machine's
state diagram as a kind of "wiring diagram" that might be used
in building a real version of that particular machine, this Logo program
is a kind of <EM>universal</EM> finite-state machine implementation.
<P><H2>Text Editors: a Use for Acceptors</H2>
<P>It may seem to you that accepting or rejecting strings isn't much
like what you usually do with computers. You may wonder how this
mathematical model is related to real computer programming. There
are two answers to this question. One is that it's possible to design
finite-state machines that have more versatile outputs than simply
yes or no. I'll give an example shortly. But the other answer is
that there are real situations in which accepting or rejecting a string
of symbols does come up in practical computation.
<P>One example is in the implementation of programming languages. When
you say that
<P><PRE>print 2+2
</PRE>
<P>is a legal Logo instruction but
<P><PRE>print 2+
</PRE>
<P>is illegal, you're doing a more complicated version of what
a finite-state acceptor does.
<P>The <EM>search</EM> command in a good text editor uses
finite-state machines. Most text editors have a command that allows
you to look through a file for a particular string of characters. Fancier
editors allow searching not just for one particular string, but for any
string that follows a rule the user can provide. The editor finds a string that
matches the rule using a finite-state machine. Of course, people who use
editors don't have to specify their search rules in the <EM>form</EM> of a
finite-state machine! The editing program accepts search rules in a simpler
form and translates them into FSM form. Here is an example, the notation
used by <EM>ed,</EM> a standard editor in the Unix operating system.
<P>A string like
<P><PRE>spaghetti
</PRE>
<P>just matches an identical string in the file you're editing. A
slightly more interesting case is
<P><PRE>[Ss]paghetti
</PRE>
<P>which matches either "Spaghetti" or "spaghetti"
(with a capital or lower case "s"). The square brackets indicate that
<EM>any</EM> of the letters inside the brackets will be accepted.
In the expression
<P><PRE>[Ss]paghet*i
</PRE>
<P>the asterisk matches <EM>any number</EM> (including zero) of the
letter before it (in this case, the letter <CODE>t</CODE>). This example
would match any of these:
<P><PRE>Spaghei
Spaghettttti
spaghetti
spagheti
</PRE>
<P>You might use this in a search command if you're a bad speller!
The bracket and asterisk can be combined;
<P><PRE>C[AD]*R
</PRE>
<P>will match any of
<P><PRE>CAR
CDR
CADDR
CR
</PRE>
<P>Or you could use
<P><PRE>M[is]*p*i
</PRE>
<P>to match the name of a famous river.
<P>Some of the rules from the game I presented earlier can be represented as
<EM>ed</EM> search strings according to these rules. In the first game the
machine accepted any string made up of <CODE>A</CODE>s and <CODE>B</CODE>s. The
corresponding <EM>ed</EM> expression is
<P><PRE>[AB]*
</PRE>
<P>The third game called for strings beginning with the sequence
<CODE>AB</CODE>, followed by whatever you like. This can be represented as
<P><PRE>AB[ABC]*
</PRE>
<P>Game 10, which I'm sure you didn't solve, accepts any string that
includes the sequence <CODE>ABCBA</CODE> within it. In <EM>ed</EM> terms, that's
<P><PRE>[ABC]*ABCBA[ABC]*
</PRE>
<P>I haven't given you a complete description of the <EM>ed</EM> search rules.
I included this much only because I want you to see how a "real" program
uses the idea of finite-state machines. But in the remaining part of this
chapter I want to use a different notation based on Logo words and lists.
<P><H2>Regular Expressions</H2>
<P>The notation I'm about to describe allows an acceptance rule, like the rules
in the <CODE>game</CODE> program or the rules for <EM>ed</EM> searches, to be
represented in Logo. The representation of such a rule is called a <EM>
regular expression.</EM> I'm going to tell you some rules for what a regular
expression can look like. Don't be confused: Any particular regular
expression is a rule that accepts strings of letters. I'm giving you rules
that accept regular expressions--rules about rules. As a rough analogy,
"one player is <CODE>X</CODE> and the other is <CODE>O</CODE>" is a rule about the
specific game Tic Tac Toe; "each player should have a fair chance to win"
is a rule about what kinds of game rules are acceptable.
<P> <EM>Alphabet rule.</EM> Any symbol in a machine's
alphabet is a regular expression. We represent the symbol as a one-letter
Logo word. In our guessing game the alphabet contains three symbols: <CODE>
A</CODE>, <CODE>B</CODE>, and <CODE>C</CODE>. So
<P><PRE>B
</PRE>
<P>is a regular expression.
<P>
<EM>Concatenation rule.</EM> A list whose members are regular expressions
represents those expressions one after another. For example, since <CODE>A</CODE>
is a regular expression and <CODE>B</CODE> is a regular expression,
<P><PRE>[A B]
</PRE>
<P>is a regular expression representing the string <CODE>AB</CODE>. (Notice
that the Logo word <CODE>AB</CODE> does <EM>not</EM> represent that string; the
alphabet rule requires that each letter be represented as a separate word.)
<P>
<EM>Alternatives rule.</EM> A list whose first member is the word <CODE>or</CODE> and
whose remaining members are regular expressions represents any string that
matches <EM>any</EM> of those expressions. For example,
<P><PRE>[OR [A A] B]
</PRE>
<P>matches either the sequence <CODE>AA</CODE> or the single symbol <CODE>B</CODE>.
As a convenience, a Logo word containing more than one letter (other
than the word <CODE>or</CODE>) is taken as an abbreviation for the <CODE>or</CODE>ing
of the individual letters. For example, <CODE>ABC</CODE> is equivalent to
<CODE>[OR A B C]</CODE>.
<P>
<EM>Repetition rule.</EM> A list containing exactly two members, in which the
first is the asterisk (<CODE>*</CODE>) symbol and the second is a regular
expression, represents a string containing any number (including zero) of
substrings that match the regular expression. So
<P><PRE>[* [OR [A A] B]]
</PRE>
<P>matches any of these:
<P><TABLE>
<TR><TD><CODE>B</CODE>
<TR><TD><CODE>BB</CODE>
<TR><TD><CODE>BAAB</CODE>
<TR><TD><CODE>AAAAAA</CODE>
<TR><TD><CODE>AABAA</CODE>
<TR><TD> (the empty string)
<TR><TD><CODE>AABBBBBAA</CODE>
</TABLE>
<P>The number of consecutive <CODE>A</CODE>s must be even for a string of
<CODE>A</CODE>s and <CODE>B</CODE>s to match this expression.
<P>These four rules constitute the definition of a regular expression.
It's a <EM>recursive definition.</EM> Just as the effect of a recursive
Logo procedure is defined in terms of a simpler case of the same procedure,
a complex regular expression is defined in terms of simpler ones.
<P>Here are the ten game rules from the beginning of this chapter in
the form of regular expressions:
<P><P>
<TABLE><TR><TH align="right">1.<TD> <CODE>[* AB]</CODE>
<TR><TH align="right">2.<TD> <CODE>[* [ABC ABC]]</CODE>
<TR><TH align="right">3.<TD> <CODE>[A B [* ABC]]</CODE>
<TR><TH align="right">4.<TD> <CODE>[* [OR [A A] [B B] [C C]]]</CODE>
<TR><TH align="right">5.<TD> <CODE>[* [ABC B]]</CODE>
<TR><TH align="right">6.<TD> <CODE>[A [* ABC] C]</CODE>
<TR><TH align="right">7.<TD> <CODE>[* [OR A B [C C]]]</CODE>
<TR><TH align="right">8.<TD> <CODE>[[* BC] [* [A [* BC] A [* BC]]]]</CODE>
<TR><TH align="right">9.<TD> <CODE>[[* AB] [* [C [OR B [A A]]] [* AB]]]</CODE>
<TR><TH align="right">10.<TD> <CODE>[[* ABC] A B C B A [* ABC]]</CODE>
</TABLE>
<P><TD> <P>
<P>You should go through these examples carefully, making sure
you understand how the regular expression represents the same idea
as the English description or the machine diagram you saw earlier.
<P><H2>Rules That Aren't Regular</H2>
<P>You may be thinking that <EM>any</EM> rule for accepting or rejecting
strings of symbols can be represented as a regular expression. But
that's not so. For example, consider the rules for recognizing ordinary
arithmetic expressions:
<P><TABLE><TR><TH align="left"><U>accepted</U>
<TH align="left"> <U>rejected</U>
<TR><TD><CODE>2+3</CODE><TD> <CODE>23+</CODE>
<TR><TD><CODE>2*(3+4)</CODE><TD> <CODE>2*)3+4(</CODE>
<TR><TD><CODE>-5</CODE><TD> <CODE>/6</CODE>
</TABLE>
<P>Think for a moment just about the matter of
balancing parentheses.
Sometimes you have parentheses within parentheses, as in
<P><PRE>((3+4)/(5+6))
</PRE>
<P>How would you represent this part of the arithmetic expression
rule in the form of a regular expression? You can't just say something like
<P><PRE>[[* (] something-or-other [* )]]
</PRE>
<P>to mean "any number of open parentheses, something, then
any number of close parentheses." That would allow strings like
<P><PRE>(((7)))))
</PRE>
<P>But this string should be rejected because it has too many close
parentheses. You're not allowed to use a close parenthesis unless you've
already used a matching open parenthesis. You can have any number of nested
parentheses you want as long as they're balanced.
<P>It is possible to invent other kinds of formal notation, more powerful than
regular expressions, that will allow us to give the rules for well-formed
arithmetic expressions. In this section I'll introduce briefly a formal
notation called <EM>production rules</EM> that's powerful enough to describe
arithmetic expressions. For now, in this chapter, I don't want to discuss
production rules in great detail; my only reason for introducing them at
this point is to give you a sense of how regular expressions fit into a
larger universe of possible formal systems. In the following sections I'll
have more to say about regular expressions and finite-state machines. But
we'll return to production rules in Chapters 5 and 6, in which we'll need
formal notations with which to discuss more interesting languages than the
<CODE>A</CODE>-<CODE>B</CODE>-<CODE>C</CODE> language of this chapter. (In Chapter 5 we'll be
talking about Pascal; in Chapter 6 we'll take on English.)
<P>The key ingredient that's missing from regular expression notation is a way
to <EM>name</EM> a kind of sub-expression so that the name can be used in
defining more complex expressions. In particular, a sub-expression name can
be used in its own definition to allow a <EM>recursive</EM> definition of the
rule.
<P>A production rule has the form
<P><PRE>name : expansion
</PRE>
<P>Each rule is a definition of the name on the left in terms of
smaller units, analogous to the definition of a Logo procedure in terms
of subprocedures. The expansion part of the rule is a string of symbols
including both members of the "alphabet" of the system (like the alphabet
that underlies a regular expression language) and names defined by
production rules.
<P>As an example, here is a set of production rules that defines the language of
arithmetic expressions. These rules take into account the "order of
operations" for arithmetic that you learned in elementary school:
multiplication before addition. An expression like
<P><PRE>2/3+1/6
</PRE>
<P>is ordinarily interpreted as the sum of two <EM>terms,</EM> namely
two thirds and one sixth. An expression can be a single term, a sum of
terms, or a difference of terms. Here's how that idea is expressed in a set
of production rules; I'll discuss the notation in more detail in a moment.
<P><CENTER><IMG SRC="xx1.gif"></CENTER>
<P>The vertical bars separate alternatives. The first rule, the one
that defines <CODE>expr</CODE>, contains three alternatives. First, an expression
can be just a single term. Second, an expression can be a smaller
expression plus a term. Third, an expression can be a smaller expression
minus a term. The symbols inside boxes are the members of the alphabet of
the arithmetic expression language. (I've put them in boxes to make it
easier not to confuse them with the punctuation characters--the colons and
vertical bars--that are part of the production rule notation itself.)
<P>Do you see how parentheses fit in? If a string like <CODE>4+5</CODE> is an
expression, then <CODE>(4+5)</CODE> is a factor, so <CODE>3*(4+5)</CODE> is a term,
and so on. Since a factor is a kind of term, and a term is a kind of
expression, the factor <CODE>(4+5)</CODE> can be considered an expression, and
so it too can be put inside parentheses. So <CODE>((4+5))</CODE> is also
acceptable as a factor.
<P><H2>Regular Expressions and Finite-State Machines</H2>
<P>I've hinted at something that I haven't actually made explicit: Regular
expressions are equivalent to finite-state machines. In other words,
if you can express a rule as a regular expression, you can design
a finite-state machine that carries out the rule. If you can't write
a regular expression for the rule, you can't design a finite-state
machine either.
<P>You may be thinking, "so what?" I've introduced two different formal
notations, finite-state machines and regular expressions, and now I'm
telling you that the two are equivalent. So why didn't I just pick one in
the first place and forget about the other? I have a general answer and a
specific answer to these questions.
<P>The general answer is that comparing different formal systems is what
automata theory is all about. By the end of this book you'll have been
introduced to half a dozen or so different formal systems. Some are more
powerful than others. The bare assertion that one formal system is
equivalent to another, or more powerful than another, isn't very interesting;
but if we can understand the <EM>reasons</EM> behind those assertions then
we may be able to put the knowledge to work in practical situations. At the
very end of this book, in Chapter 6, we'll talk about a particular formal
system that's often used in artificial intelligence programs to recognize
English sentences. By then you should know enough about formal systems to
be able to understand why that particular one is a good choice.
<P>The specific answer is that finite-state machines and regular expressions
are <EM>different</EM> from each other in an interesting way. A finite-state
machine is an <EM>algorithm,</EM> a sequence of steps, or a procedure that can
be followed to test whether some string matches a given rule. It says,
"start here, then if this happens do this, then..." just like a procedure
in Logo or most other programming languages. (But we've seen that a
finite-state machine is like a procedure written in a restricted programming
language that isn't as flexible as Logo.) A regular expression, though, is
<EM>not</EM> a sequence of steps. It's more like a description of the <EM>
result</EM> that we want, leaving open the precise recipe for how to get there.
People often pose problems in a similar way. They call the plumber and say,
"the drain in my bathtub is backing up." Part of the plumber's expertise is
to be able to translate that <EM>declarative</EM> problem statement into a
<EM>procedural</EM> form, a sequence of steps needed to clear up the problem.
An early stumbling block in artificial intelligence research was the seeming
gulf between the procedural knowledge embodied in a computer program and the
declarative knowledge needed for human-like behavior. Recently people have
invented <EM>declarative programming languages</EM> (the best known
is Prolog, but any commercial spreadsheet program is also
in this category) that
allow the user to state a problem in declarative form. The programming
language interpreter then automatically translates this problem statement
into a sequence of steps for the computer to perform.
<P>Writing a Prolog interpreter raises many issues beyond the scope of this
book. But we can take a smaller step in the realm of translation from
a declarative notation to a procedural one. I've written a Logo program,
listed at the end of the chapter, that translates from a regular
expression to an equivalent finite-state machine. Its top-level procedure,
<CODE>machine</CODE>, takes a regular expression as input and outputs a machine
list in the format I showed earlier.
<P><H2>How to Translate</H2>
<P>The general claim that regular expressions are equivalent in power
to finite-state machines is called Kleene's Theorem, named after the
mathematician Stephen C. Kleene, its discoverer. You can find a proof
of this theorem in any textbook on automata theory. I'm not going
to give a proof here, but I'll indicate how the translation is done
in my program. The same kinds of ideas are used in the proof.
<P>Remember that there are four parts to the definition of a regular expression.
The alphabet rule provides the fundamental building blocks; the
concatenation, alternatives, and repetition rules build large regular
expressions recursively out of smaller ones. The translation process
follows the same pattern: We start with a procedure to build a trivial
two-state machine that only accepts a single letter, then we add three
rules for combining smaller machines into a large machine. In the following
paragraphs I'll show how each rule is reflected in the
<A HREF="v3ch1.html#machine"><CODE>machine</CODE></A> program.
<P>This construction process often produces machines with more states than
necessary. The <CODE>machine</CODE> program eliminates redundant states as its
final step.
<P>The alphabet rule says that any member of the machine's alphabet is
a regular expression. In the program, a symbol can be any one-letter word other
than <CODE>*</CODE>. The symbol <CODE>X</CODE> is translated into the machine
<P><PRE>[1 [[1 X 2]] [2]]
</PRE>
<P>(You'll see that the program works by combining little machines
into bigger ones. Every time the program has to invent a new machine
state it uses the next free number. So the state numbers might not
be 1 and 2 in a real example.) The procedure
<A HREF="v3ch1.html#ndletter"><CODE>ndletter</CODE></A> handles this
rule.
<P>Next comes the <EM>concatenation rule.</EM> The regular expression
<P><PRE>[A B]
</PRE>
<P>matches a string with two parts; the
first substring matches the <CODE>A</CODE> and the second matches the <CODE>
B</CODE>. In this simple example each "substring" matches only a single
letter. In a more complicated concatenation like
<P><PRE>[[OR A C] [* B]]
</PRE>
<P>there are different choices for each substring. For example, that
regular expression is matched by the string
<P><PRE>CBBB
</PRE>
<P>in which the letter <CODE>C</CODE> matches the first part of the
expression and the substring <CODE>BBB</CODE> matches the second part.
<P>To translate a regular expression of this kind (a concatenation) into a
finite-state machine, we begin by recursively translating the subexpressions
into smaller machines. Then we have to "splice" the two machines together.
Procedure <A HREF="v3ch1.html#ndconcat"><CODE>ndconcat</CODE></A> does this splicing.
<P>We'll begin with the simplest possible example. Suppose we want to
translate the regular expression
<P><PRE>[A B]
</PRE>
<P>We have already translated the two symbols <CODE>A</CODE> and <CODE>B</CODE> into
machines:
<P><CENTER><IMG SRC="concat-before.gif" ALT="figure: concat-before"></CENTER>
<P>The combined machine must start at the start state of the first
component machine, state 1. The combined machine should be in an accepting
state when <EM>both</EM> component machines have been satisfied; in other
words, the accepting states of the combined machine should be those of the
<EM>second</EM> component machine. In this case that means only state 4.
<P>To splice the component machines together we must add transitions (arrows)
between them. Specifically, whenever the first component machine gets into
an accepting state, the combined machine should follow the same transitions
that apply to the start state of the second component machine. In this
case, when the combined machine gets into state 2 (the accepting state of
the first component machine) it should follow the same transitions that
apply to state 3 (the start state of the second machine). There is only one
such transition, a <CODE>B</CODE> arrow into state 4. That means we must add the
arrow
<P><PRE>[2 B 4]
</PRE>
<P>to the combined machine.
<P><CENTER><IMG SRC="concat-after.gif" ALT="figure: concat-after"></CENTER>
<P>State 3, although it is still in the machine, is now useless.
There is no way for the machine to get into state 3. Later
in the translation process another procedure removes
such "orphaned" states from the machine.
<P>As a slightly more complicated example, consider the translation of the
regular expression
<P><PRE>[[OR A C] [* B]]
</PRE>
<P>We start by supposing that we've already translated the two
subexpressions separately:
<P><CENTER><IMG SRC="concat2-before.gif" ALT="figure: concat2-before"></CENTER>
<P>(We haven't yet discussed the alternatives rule or the repetition
rule, so I haven't yet explained how these subexpressions are translated.
For now, please just take on faith that this picture is correct. We'll get
to those other rules shortly.)
<P>The start state of the combined machine is the start state of the first
component, state 1. At every accepting state of the first machine we must
duplicate the transitions from the start state of the second machine. In
this example the start state of the second machine has only the transition
<P><PRE>[4 B 5]
</PRE>
<P>but there are two accepting states in the first machine, so we
must add two new arrows:
<P><PRE>[2 B 5] [3 B 5]
</PRE>
<P>A final detail is that in this example the start state of the
second component machine, state 4, is an accepting state. That means that
the second substring can be empty. Therefore the accepting states of the
first component machine should also be accepting states of the combined
machine. Here is the result:
<P><CENTER><IMG SRC="concat2-after.gif" ALT="figure: concat2-after"></CENTER>
<P>Again, state 4 is now an "orphan" and will be eliminated
later in the program.
<P>The <EM>alternatives rule</EM> combines two machines in parallel, so to speak,
rather than in series. It works by inventing a new state
that becomes the start state of the combined machine. Arrows leaving
from the new state duplicate the arrows from the start states of the
component machines. Procedure <A HREF="v3ch1.html#ndor"><CODE>ndor</CODE></A> handles this rule.
<P>As an example, here is the translation process for
<P><PRE>[OR A B]
</PRE>
<P>(or its abbreviation <CODE>AB</CODE>). We start with two separate machines:
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v3ch1/alter-before.gif" ALT="figure: alter-before"></CENTER>
<P>We combine them by inventing a new state 5:
<P><CENTER><IMG SRC="alter-after.gif" ALT="figure: alter-after"></CENTER>
<P>I haven't explained all the details of the construction process.
For example, should the new state, state 5, be an accepting state? In this
example it shouldn't be. See if you can think of a case where it might be;
then read the program listing to see the exact algorithm that makes this
decision. Again, this construction process may leave unused states for
later cleanup.
<P>A much more serious problem is that an <CODE>or</CODE> construction is likely to
produce a nondeterministic machine. For example, here is the machine
for
<P><PRE>[OR [A B] [A C]]
</PRE>
<P><CENTER><IMG SRC="or-nondet.gif" ALT="figure: or-nondet"></CENTER>
<P>Like the unused states, the problem of nondeterminism is
left for the end of the program, when procedure <CODE>determine</CODE> translates
the nondeterministic machine into a deterministic one.
(The concatenation rule can also make nondeterministic machines, although
it's not as likely.)
<P>The final case to be considered is the <EM>repetition rule.</EM> This rule
acts on only one smaller machine, not two machines as in the previous
two cases. The rule doesn't require any new states. It has two effects.
One is to add the start state to the list of accepting states. The
second is to add arrows from the (old) accepting states that mimic
the arrows from the start state. (This is exactly like the splicing
of two machines in the concatenation rule, but in this case we concatenate
a single machine with itself!) Procedure <A HREF="v3ch1.html#ndmany"><CODE>ndmany</CODE></A>
makes this transformation.
It, too, can result in a nondeterministic machine.
<P>Here is an example of the rule:
<P><CENTER><IMG SRC="repetition.gif" ALT="figure: repetition"></CENTER>
<P>These four rules are combined by <A HREF="v3ch1.html#nondet"><CODE>nondet</CODE></A>,
a procedure whose input is
a regular expression and whose output is a (possibly nondeterministic) machine.
<P><PRE>to nondet :regexp
if and (wordp :regexp) (equalp count :regexp 1) [output ndletter :regexp]
if wordp :regexp [output ndor reduce "sentence :regexp]
if equalp first :regexp "or [output ndor butfirst :regexp]
if equalp first :regexp "* [output ndmany last :regexp]
output ndconcat :regexp
end
</PRE>
<P>The top-level procedure <A HREF="v3ch1.html#machine"><CODE>machine</CODE></A>
does a little initialization
and then does its work with the instruction
<P><PRE>output optimize determine nondet :regexp
</PRE>
<P>That is, first it creates what may be a
nondeterministic machine,
then if necessary it translates that into a deterministic one (eliminating
orphan states in the process), then it gets
rid of any redundant states that may have been created.
<P><H2>Making the Machine Deterministic</H2>
<P>In the first volume of this series we explored the techniques of depth-first
and breadth-first tree traversal. Given a tree structure, these algorithms
allow us to "visit" every node of the tree once.
<P>A finite state machine can be viewed as a structure almost like a tree.
The machine's start state corresponds to the root node; the states that
can be reached by an arrow from a given state are the children of that state.
But there is one important difference between trees and machines: In a tree,
every node (except for the root node) has exactly one parent. The tree
search algorithms depend on that fact to ensure that each node is visited
only once. In a machine, arrows from several different states can lead to
the same state, so a state may have several "parents." The technical name
for an arbitrary collection of nodes with connections among them is a
<EM>graph.</EM> If the connections are one-way, as in the finite
state machine diagrams, it's called a <EM>directed graph.</EM>
<P>Searching a graph is just like searching a tree, except that we have to
keep track of which nodes we've already visited, to avoid examining the
same node twice. Procedure <A HREF="v3ch1.html#determine"><CODE>determine</CODE></A>
creates a list named <CODE>states</CODE>, initially
empty, into which each state number is added as the
program examines that state. The depth first traversal of the machine
is carried out by procedure <A HREF="v3ch1.html#nd.traverse"><CODE>nd.traverse</CODE></A>;
although this procedure looks different from the
<A HREF="../v1ch14/v1ch14.html#depth.first"><CODE>depth.first</CODE></A>
procedure in Volume 1, it
uses the same basic algorithm. Given a state as input, it processes
that state and invokes itself recursively for all of the children of
that state--the states reachable by arrows from the input state. Unlike
<CODE>depth.first</CODE>, though, <CODE>nd.traverse</CODE> is an operation. It
outputs a new list of moves (arrows) for the deterministic version of
the machine.
<P>What does it mean to process a state? <CODE>Nd.traverse</CODE> first checks
whether this state has already been processed; if so, it outputs an empty
list, because this state will contribute no new moves to the machine.
Otherwise, it remembers this state number as having been processed, finds
all the moves starting from this state, and calls
<A HREF="v3ch1.html#check.nd"><CODE>check.nd</CODE></A> to look for
nondeterminism. <CODE>Check.nd</CODE> takes the first available arrow whose tail
is at the state we're processing, and looks for all arrows with the same
tail and with the same letter.<SUP>*</SUP>
The local variable <CODE>heads</CODE> will contain a list of all the state numbers
reachable by these arrows. (The state numbers are sorted into increasing
order, and duplicates eliminated. If the machine has two completely
identical arrows, that doesn't result in nondeterminism.)
<P><SMALL><BLOCKQUOTE><SMALL><SUP>*</SUP>By the way, <CODE>nondet</CODE> always
creates arrows with only a single letter; if two or more letters lead from
the same state to the same state, a separate arrow is created for each of
them. This makes for a longer machine list, but makes steps like this
one--looking for two arrows with the same letter--easier. Once the
deterministic machine has been created, procedure <CODE>optimize</CODE> will combine
such arrows into the abbreviated form with
more than one letter per arrow.</SMALL></BLOCKQUOTE></SMALL>
<P>There are
three cases for what <CODE>check.nd</CODE> must do. First, if there is
only one state number in <CODE>:heads</CODE>, then there is no nondeterminism for
this letter, and <CODE>check.nd</CODE> includes the arrow from the original
machine as part of the deterministic machine. Second, if there is more
than one state number, <CODE>check.nd</CODE> looks to see if we've already seen
the same combination of result states. If so, then we've already created
a new state equivalent to that combination of old states, and <CODE>check.nd</CODE>
creates a new arrow pointing to that existing new state. Finally, the third
case is that this combination of states is one we haven't seen before. In
that case, <CODE>check.nd</CODE> must create a new state, with arrows duplicating
those from all of the original states.
<P>In other words, if there are arrows
<P><PRE>[[3 B 4] [3 B 7]]
</PRE>
<P>then <CODE>check.nd</CODE> will invent a new state that is an "alias"
for "four-and-seven." If the same machine also contains arrows
<P><PRE>[[8 C 4] [8 C 7]]
</PRE>
<P>then <CODE>check.nd</CODE> will use the <EM>same</EM> alias state for this
pair, not inventing a new one. The new
state is given arrows matching those of all its component states (4
and 7 in this example). The new state might itself contain a nondeterministic
branch, but that's okay because the new state will eventually be processed
as we continue to traverse the machine graph.
<P>You might think that this process could go on forever: that each new
state <CODE>check.nd</CODE> invents will turn out to include nondeterminism, which
will require yet another new state to resolve. Fortunately, that
doesn't happen; the process does always end eventually. (In the next
chapter we'll see what the limit is on the number of necessary states
for the deterministic machine.)
<P>Because <CODE>determine</CODE> uses a graph traversal algorithm to examine
the original machine's states, it will never find "orphan" states
that can't be reached by arrows from some other state. That's why
the process of making the machine deterministic also eliminates orphan
states, with no extra effort.
<P><H2>Eliminating Redundant States</H2>
<P>The machines produced by <CODE>determine</CODE> are runnable, but often ugly;
they contain many more states than necessary. Procedure
<A HREF="v3ch1.html#optimize"><CODE>optimize</CODE></A>
eliminates many redundancies and also combines arrows with the same
head and tail but with different letters.
First it goes through the machine's arrow list,
creating a list for each state representing the exits from that state:
<P><CENTER><IMG SRC="optimize.gif" ALT="figure: optimize"></CENTER>
<PRE> [[* [A B]] C]
State 1: [[A 2] [C 4]]
State 2: [[B 3]]
State 3: [[A 2] [C 4]]
State 4: []
</PRE>
<P>In this machine, states 1 and 3 have the same exit list.
(In these lists, each arrow is represented with only two members; the
arrow's tail is not included. That's because states 1 and 3 would <EM>
not</EM> have identical lists if the tails were included. State 1's list
would be
<P><PRE>[[1 A 2] [1 C 4]]
</PRE>
<P>and state 3's list would have arrows starting with 3. In the
program, the two-member form of an arrow is called a <EM>stub.</EM>)
<P>The program must be careful about the order in which it puts stubs
in each state's list, so it doesn't end up with
<P><PRE>[[C 4] [A 2]]
</PRE>
<P>for one of the states. That's why <A HREF="v3ch1.html#stub.add"><CODE>stub.add</CODE></A>
takes trouble
to insert each stub in a well-defined position, rather than just adding
each new stub at the beginning or end of the list. It's also in
<CODE>stub.add</CODE> that arrows connecting the same two states but with different
letters are combined into a single arrow.
<P>Since states 1 and 3 also agree in their acceptingness (namely they aren't
accepting states), they can be combined into one state. <CODE>
Optimize.state</CODE> can replace every reference to state 3 with a reference to
state 1.
<P><H2>A Finite-State Adder</H2>
<P>I promised earlier to show you a use for finite-state machines other
than accepting or rejecting strings. In this section I'll fulfill
that promise by designing a machine to add two numbers. We'll represent
the numbers in binary notation, in which each digit represents a power
of 2 instead of a power of 10.
<P>If you've come across binary numbers before, you can skip this paragraph.
Just as the ordinary notation for numbers is based on the ten digits 0 to 9,
binary notation is based on <EM>two</EM> digits, 0 and 1. In ordinary
("decimal") notation, the amount that each digit contributes to the total
depends on where it is in the number. For example, in the number 247, the
digit 2 contributes two hundred, not just two, because it's in the third
position counting from the right. Each digit's contribution is the value of
the digit itself multiplied by a power of ten:
<P><CENTER>2×10<SUP><SMALL>2</SMALL></SUP>
+ 4×10<SUP><SMALL>1</SMALL></SUP>
+ 7×10<SUP><SMALL>0</SMALL></SUP></CENTER><P>
(10<SUP><SMALL>2</SMALL></SUP> is 100; 10<SUP><SMALL>1</SMALL></SUP> is 10; 10<SUP><SMALL>0</SMALL></SUP> is just 1.) In binary, the
contribution of each digit is multiplied by a power of <EM>two,</EM> so the
binary number 10101 represents
<P><CENTER>1×2<SUP><SMALL>4</SMALL></SUP>
+ 0×2<SUP><SMALL>3</SMALL></SUP>
+ 1×2<SUP><SMALL>2</SMALL></SUP>
+ 0×2<SUP><SMALL>1</SMALL></SUP>
+ 1×2<SUP><SMALL>0</SMALL></SUP></CENTER><P>
which is 16+4+1 (2<SUP><SMALL>4</SMALL></SUP>+2<SUP><SMALL>2</SMALL></SUP>+2<SUP><SMALL>0</SMALL></SUP>) or 21. Computers use binary notation
because it's easy to build electrical circuits in which each wire is either
on or off. In Chapter 2 we'll talk about an example. Right now I want to
show something different--not an actual electronic machine but an abstract
machine based on the ideas we've been using in this chapter.
<P>The machine will add two binary numbers, one digit position at a time, just
the way you add multi-digit numbers yourself. When you see a problem like
<P><CENTER><TABLE><TR><TD align="right">376
<TR><TD align="right"><U>+572</U></TABLE></CENTER><P>
you start at the right and say, "6 plus 2 is 8; 7 plus 7 is 14, which is
4 carry 1; 1 plus 3 plus 5 is 9." The finite-state adder works the same
way except that the digits are always 0 or 1.
<P>The machine will add any numbers, but to explain how it works I want to
consider a specific example. Let's say we want to add 52 and 21. (By the
way, I didn't pick these numbers because they name card games, but because
the pattern of digits in their binary forms is convenient for the
explanation I want to give.) 52 in binary is 110100 (32+16+4) and 21 is
10101 (16+4+1). I'm going to write these one above the other, with a couple
of extra zeros on the left to leave room for a possible carry:
<P><PRE> 0 0 1 1 0 1 0 0
0 0 0 1 0 1 0 1
</PRE>
<P>Remember how a finite-state machine works: At a given moment it's
in some <EM>state,</EM> then it reads some <EM>input</EM> symbol and goes to
another state. In this problem, since we have two numbers to add, the most
natural way to think about it would be to give the machine <EM>two</EM> inputs
at a time. This idea doesn't quite fit in with the formal definition of a
finite-state machine, but we can let the machine's "alphabet" consist of
<EM>pairs</EM> of digits, so something like <CODE>01</CODE> would be a single input.
(By the way, the word <EM>bit</EM> is commonly used as an abbreviation for
"binary digit.") Just as you added vertical pairs of digits (first 6 and 2,
then 7 and 7, and so on) in the earlier example, we'll use vertical pairs of
bits as the inputs to the finite-state adder, starting from the right end.
So the first input will be 01, then 00, then 11, then 00, then 11 again,
then 10, and then 00 twice. From now on, in this section, when you see
something like 10 you should remember that it is a <EM>single</EM> input to
the finite-state machine, a single symbol, not two in a row.
(In the diagram below, an arrow labeled <CODE>01/10</CODE> represents two
arrows, one for the input <CODE>01</CODE> and one for the input <CODE>10</CODE>. These
two arrows will always go to the same state because 0+1=1+0.)
<P>We need to make one change in the notation used in machine diagrams.
We no longer want to mark each state as accepting (double circle)
or rejecting (single circle). Instead, each state produces an <EM>
output</EM> that can be any arbitrary symbol. In this machine the outputs
will be 0 or 1, representing the binary digits of the sum. Inside
each state circle, instead of just a state number you'll see something
like "3/1"; this means that it's state number 3 and that the output
from that state is 1.
<P>Here is the machine:
<P><CENTER><IMG SRC="fsm-add.gif" ALT="figure: fsm-add"></CENTER>
<P>State 1, the start state, has no output. When the machine is in start
state it hasn't seen any digits of the addends yet, so it can't compute
a digit of the sum. States 2 and 4 output a zero digit, while states
3 and 5 output a one. (Like the inputs, the number that the machine
outputs is presented with its rightmost bit first. The machine works
this way for the same reason that <EM>you</EM> add numbers from right
to left: That's the direction in which a "carry" digit moves from
one column to another.)
<P>Why are there <EM>two</EM> zero-output states and <EM>two</EM> one-output
states? The reason is that the machine is in state 4 or 5 when there
is a carry into the next digit of the sum.
<P>Let's trace through my example. We start in state 1. The first input
symbol is 01, representing a 0 in the rightmost (binary) digit of 52
and a 1 in the rightmost digit of 21. The machine enters state 3
and outputs a 1.
<P>The next input is 00 because both numbers have zero as the second
digit. The machine enters state 2 and outputs 0.
<P>The next input is 11. The machine enters state 4 and outputs 0. Being in
state 4 means that there is a carry from this position into the next.
<P>You can finish the example yourself. The sum should be 01001001,
or 73.
<P><H2>Counting and Finite-State Machines</H2>
<P>Earlier we saw that you can't write a regular expression for a rule
that requires balanced parentheses. Since regular expressions are
equivalent to finite-state machines, you won't be surprised to learn
that finite-state machines can't count.
<P>
Actually, they can count up to a point; it's just that each finite-state
machine can only count up to a fixed limit. For example, here is
a finite-state machine that accepts strings of balanced parentheses
up to four deep:
<P><CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v3ch1/fourdeep.gif" ALT="figure: fourdeep"></CENTER>
<P>This machine will accept strings like these:
<P><PRE> () (()) ()()
(()()) (((()))) (((())))(())
</PRE>
<P>There is no limit to the <EM>length</EM> of the string this
machine can handle. For example, it will accept this:
<P><PRE> ()()()()()()()()()()()()()()
</PRE>
<P>But there can be no more than four parentheses open <EM>
at once</EM>; the machine will reject
<P><PRE> ((((()))))
</PRE>
<P>Even this limited counting ability of finite-state machines is of great
practical value. Real computers, after all, are finite-state
machines. Any real computer has a finite amount of memory, and this
memory can be in a finite number of states. But the number is quite
huge. If a real computer includes a parenthesis-counting program
that is limited to, say, 20,000 levels of parentheses, nobody will
ever notice that the limit isn't infinite.
<P>(The number of states in a real computer may be even larger than you're
thinking. Each bit of computer memory isn't a state. Instead, if
a computer has <EM>n</EM> bits of memory it has 2<SUP><SMALL>n</SMALL></SUP> states! For
example, a computer with three bits of memory can use those bits to
represent <EM>eight</EM> states:
<P><PRE>0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
</PRE>
<P>The number of possible states in a typical large computer
is greater than the number of atoms in the galaxy.)
<P>In a moment I'm going to talk about a theoretical model of a machine
with infinite memory. You might wonder why it pays to study such
machines, since any real machine has to be limited in memory. The
answer has to do with my example about the 20,000 levels of parentheses.
It is theoretically possible to write a regular expression for such
strings. To show you how it's done, here is a regular expression
for up to three levels:
<P><CENTER><IMG SRC="xx2.gif"></CENTER>
<P>(I've drawn boxes around the actual alphabet-rule symbols just to
make it a little easier for you to distinguish between the parentheses,
which are symbols in the input strings, and the brackets, which are part of
the glue that holds a regular expression together.)
<P>There is no theoretical problem about extending this regular expression
to allow up to 20,000 parentheses. But a machine based on this technique
would be very large and complicated. Instead, it makes more sense to
<EM>pretend</EM> that the computer has an infinite amount of memory available
and use a formal system (like the production rules I mentioned briefly)
that depends on an infinite memory. Such a formal system leads to
a shorter, more elegant expression of the balanced parentheses rule.
In practice, we can provide enough memory for any of the strings our
program will actually meet.
<P><H2>Turing Machines</H2>
<P>One way we might explore infinite machines is to imagine that they're
represented by state diagrams, like those of finite-state machines,
but with an infinite number of states. For example, here is a picture
of an infinite-capacity parenthesis counter:
<P><CENTER><IMG SRC="waydeep.gif" ALT="figure: waydeep"></CENTER>
<P>The trouble with this idea is that it's hard to model precisely what's
meant by that row of dots on the right. There's no way we can have
a <EM>complete</EM> formal description of an infinitely complex machine.
<P>Instead, consider what <EM>you</EM> do when you have to solve a problem
too complex to fit in your own memory. You don't build yourself a
bigger brain; you get a pencil and some paper. That is, you use <EM>
external</EM> storage. You can imagine that your brain is a finite-state
machine but that it has access to an infinite supply of paper.
<P>Of course, this division of a problem's necessary information into
a finite <EM>internal</EM> state and an infinite <EM>external</EM> memory
also models actual computers in an obvious way. The internal state
in the model represents the internal memory of the computer, while
the external memory in the model represents such storage devices as
disks and tapes. To solve a bigger problem you don't have to buy
a bigger computer; you just have to switch floppy disks occasionally.
<P>You might think that the mathematical model I'm talking about was
based on the analogy with real computers and that my story about the finite-state
brain is just a coincidence. But in fact this model was invented
by Alan M. Turing in 1936, before there were any computers! It was
<EM>human</EM> problem-solving that Turing wanted to model with a machine.
<P>What is a Turing machine? Start by imagining a finite-state machine
with different possible outputs, like the adder we saw earlier. Attached
to this machine is a tape of limitless length. Symbols from some
alphabet, like the machine's input and output symbols, can be written
on the tape. There is a reading and writing mechanism, like the heads
of a magnetic tape recorder, that can travel along the tape.
<P>Just as each state of the machine can have an output associated with
it, each state can also take action to affect the tape: It can move
the head by one symbol in either direction and it can change the
symbol at the head's current position.
<P>In fact, we simplify the formal description of the machine by
using the tape as the input/output device as well as the storage device.
That is, we can start with some sequence of symbols already written
on the tape. That sequence serves as the input to the machine; state
transitions are based on the symbol under the tape head, not a symbol
from some other source. Likewise, the output from a state (if any)
is written on the tape.
<P>Somewhat analogous to the concept of an accepting state in our earlier
examples, a Turing machine can have <EM>halting</EM> states. When the
machine enters a halting state it stops its operation. There are
no more state transitions. The output from the machine is whatever
sequence of symbols it leaves written on the tape.
<P><H2>Turing's Thesis</H2>
<P>Turing invented his abstract machine because he was trying to formalize
the idea of an <EM>effective procedure</EM>: What does it mean to specify
a technique for solving some problem well enough that we can be sure
it will really work? As an analogy, think about directions for driving
from here to somewhere. Someone can hand you a piece of paper with
a list of instructions like "When you get to the gas station
on the left, turn right." But sometimes you get directions that
weren't careful enough. There may be a sharp right turn and a mild
right turn available near the gas station. There may be a fork in
the road before you even get to the gas station.
<P>Turing's idea is that any problem for which there is <EM>any</EM> effective
procedure can be modeled by a Turing machine. The phrase "any effective
procedure" is taken to include the workings of the human mind. If
Turing is right, any problem that a person can solve can be programmed
for a computer.
<P>This claim isn't something that can be proved or disproved mathematically
because there is no prior formal definition of "effective procedure"
to which Turing machines can be compared. Also, it may be that the
idea of a procedure somehow doesn't cover all the different kinds
of thinking that people do. Maybe it's true, for example, that computers
are potentially as powerful as people at solving problems, but "solving
problems" might not turn out to be an appropriate description of
what's going on when we feel emotions. If that turned
out to be true, we <EM>should</EM> expect a computer to become the world's
chess champion someday, but we <EM>shouldn't</EM> expect one to become
the world's champion poet.
<P>But this possible conclusion has been attacked from both sides. Some
people think that emotions really <EM>are</EM> a matter of computable
procedures. Kenneth Colby's program called Parry attempts to model
the behavior of a paranoid human being by manipulating variables
for emotions like anger and fear. On the other hand, some people
think that even chess doesn't fall within the realm of things that
people do by carrying out effective procedures in Turing's sense.
A chess master, these people say, doesn't analyze the chess board
in a step-by-step fashion like a computer. He looks at the board
as a single, whole entity, and the important features just spring
to mind by some process that is still rather mysterious.
<P>What <EM>is</EM> known is that several other mathematical models of effective
procedures have been shown to be equivalent to Turing machines, in
the same sense in which regular expressions are equivalent to finite-state
machines. For example, all of the popular programming languages are
Turing-equivalent. There's no such thing as a computation that can
be done in Logo but not in Pascal, or vice versa. (Of course, one
language may be more <EM>convenient</EM> than another for a given problem.)
<P><H2>The Halting Theorem</H2>
<P>I'm not going to get into specific examples of Turing machine programming
here. That would take too much space for a single chapter; if you're
interested you should pursue the topic in a book on automata theory.
But I want to give one example of the theoretical value of Turing machines.
<P>You've undoubtedly had the experience of writing a Logo program with a bug
that causes an "infinite loop"--you run the program and it just sits there
forever, when instead it's supposed to compute and print some results.
That's a frustrating kind of bug because you're never quite sure if the
program is really broken or if it's just very slow. Maybe if you waited
another minute it would come up with the answer. Wouldn't it be great if,
when you started the program running, Logo could print an error message like
<CODE>This program has an infinite loop</CODE>, just as it does for other errors?
<P>It turns out that infinite loops can't, in general, be detected
automatically. Certainly <EM>some</EM> infinite loops are very easy to spot,
and we can write programs that catch certain categories of infinite loop.
But we can't write a program that's <EM>guaranteed</EM> to catch infinite
loops in programs, in Logo or any other Turing-equivalent language. The
fact that it's impossible is called the <EM>halting theorem.</EM>
<P>It's a little tricky understanding just what the halting theorem says because
it involves Turing machines that manipulate Turing machines as data, which
is a kind of self-reference akin to recursion. Self-reference is always hard
to talk about and can lead to paradoxes like the classic "This statement
is false." (Is the sentence in quotes true or false? If it's true, then it
must be false, because it says so. But if it's false, and it <EM>says</EM>
it's false, it must really be true!) So let's proceed carefully.
<P>The data recorded on a Turing machine's tape is a string of symbols.
Generally we choose the symbols to represent something meaningful; for
example, a string of digits can represent a number. Earlier in this chapter
we used strings of symbols like
<P><PRE>[1 [[1 A 2] [2 B 3] [3 A 2]] [1 3]]
</PRE>
<P>to represent a finite-state machine. There's no reason we
couldn't put <EM>that</EM> string of symbols on the tape of a Turing machine
as its input. For example, we could build a Turing machine that would work
like my <CODE>fsm</CODE> program, simulating the finite-state machine that it found
written on its tape when it started.
<P>Letting a Turing machine simulate a finite-state machine doesn't raise
questions of self-reference. But a Turing machine, too, is a formal
structure; it, too, can be represented as a string of symbols.
<P>Because a representation of a Turing machine can be the input to another
Turing machine, we can design Turing machines that answer questions about
Turing machines. For example, we can write a <EM>universal</EM> Turing
machine, one that simulates any Turing machine the way <CODE>fsm</CODE> simulates
any finite-state machine.
<P>A universal Turing machine (a Turing machine simulator) sort of half-solves
the halting problem. Suppose we want to know whether a given machine will
halt after it is started with a given input. (This is like asking whether a
certain Logo procedure will terminate if it's invoked with a particular
input.) We can use the universal Turing machine to simulate the one we're
interested in. If the machine <EM>does</EM> halt, we'll find out about it.
But if the machine in question <EM>doesn't</EM> halt, then the simulator
won't halt either. We'll still have the problem we had in the first
place--how can we be sure it won't finally halt if we give it another
minute?
<P>To solve the halting problem, what we need is a Turing machine that accepts
a representation of any Turing machine as input, just like the universal
Turing machine. But this one has to be guaranteed to halt, even if the
input machine wouldn't halt. That's what the halting theorem says we can't
do.
<P><H2>Proving the Halting Theorem in Logo</H2>
<P>What makes it possible to raise the question of whether a Turing machine can
decide whether another Turing machine would halt for a given input tape is
the fact that one Turing machine's "program" can be represented as data
for another Turing machine. This is also true of Logo procedures. In
particular, the higher-order procedures like <CODE>map</CODE> and <CODE>filter</CODE>
manipulate other procedures by accepting their names as inputs.
We can, therefore, use Logo
procedures to illustrate the proof of the halting theorem.
<P>We'll consider a Logo procedure with an input as analogous to a Turing
machine with its input tape. We want to prove that there can't be a Logo
procedure that could tell whether such a procedure stops for a given input.
The technique we use is called <EM>proof by contradiction.</EM> In this
technique we assume that there <EM>is</EM> such a procedure, then show that
this assumption leads to a paradox.
<P>So let's imagine that someone has written a Logo predicate <CODE>haltp</CODE> that
takes two inputs: the name of a procedure and an input value for that
procedure. <CODE>Haltp</CODE> will output <CODE>true</CODE> if the procedure it's testing
would eventually stop, given the specified input; <CODE>haltp</CODE> outputs <CODE>
false</CODE> if the procedure it's testing would get into an infinite loop, like a
recursive procedure without a stop rule. (In practice, if you think about
your own experience debugging programs, it's easy to tell if a procedure
doesn't have a stop rule at all, but not so easy to be sure that the stop
rule will always eventually be satisfied. Think about a Pig Latin program
given a word of all consonants as input. We want
<P><PRE>to piglatin :word
if memberp first :word [a e i o u] [output word :word "ay]
output piglatin word bf :word first :word
end
? <U>print haltp "piglatin "salami</U>
true
? <U>print haltp "piglatin "mxyzptlk</U>
false
</PRE>
<P>Remember that <CODE>haltp</CODE> itself must <EM>always</EM> stop, even
in the case where <CODE>piglatin</CODE> wouldn't stop.)
<P>Now consider this Logo procedure:
<P><PRE>to try :proc
if haltp :proc :proc [loop]
end
to loop
loop
end
</PRE>
<P>Since <CODE>haltp</CODE> works, we're assuming, on <EM>any</EM> Logo
procedure with one input, it must work on <CODE>try</CODE> in particular.
What happens if we say
<P><PRE>? <U>try "try</U>
</PRE>
<P>Does this stop or loop? Suppose it stops. <CODE>try</CODE> begins its
work by evaluating the expression
<P><PRE>haltp "try "try
</PRE>
<P>Since we've said <CODE>try</CODE> will stop, given <CODE>try</CODE> as input,
<CODE>haltp</CODE> will output <CODE>true</CODE>. It follows, from the definition of <CODE>
try</CODE>, that <CODE>try</CODE> will invoke <CODE>loop</CODE> and will <EM>not</EM> stop.
Similarly, if we start with the assumption that <CODE>try</CODE> will loop, then
<CODE>haltp</CODE> must output <CODE>false</CODE> and so, from the definition of <CODE>
try</CODE>, you can see that <CODE>try</CODE> <EM>will</EM> stop. Whatever value <CODE>
haltp</CODE> outputs turns out to be incorrect.
<P>It was the assumption that we could write an infallible <CODE>haltp</CODE> that led
us into this contradiction, so that assumption must be wrong. We can't write
a Logo procedure that will automatically detect infinite loops in our
programs. A similar proof could be made in any language in which one program
can manipulate another program as data--that is, in any Turing-equivalent
language.
<P>
<TABLE width="100%"><TR><TD><A HREF="../v3-toc2.html">(back to Table of Contents)</A>
<TD align="right"><A HREF="../v3ch0/v3ch0.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v3ch2/v3ch2.html"><STRONG>NEXT</STRONG></A>
</TABLE>
<P><H2>Program Listing</H2>
<P><P>
<P><PRE>
;;; Finite State Machine Interpreter (<A NAME="fsm">FSM</A>)
to game :which
fsm thing word "mach :which
end
to fsm :machine
cleartext
setcursor [0 3]
localmake "start startpart :machine
localmake "moves movepart :machine
localmake "accept acceptpart :machine
fsm1 :start
end
to fsm1 :here
ifelse memberp :here :accept [accept] [reject]
fsm1 (fsmnext :here readchar)
end
to fsmnext :here :input
blank
if memberp :input (list char 13 char 10) ~
[print ifelse memberp :here :accept ["| ACCEPT|] ["| REJECT|]
output :start]
type :input
catch "error [output last find [fsmtest :here :input ?] :moves]
output -1
end
to fsmtest :here :input :move
output and (equalp :here arrowtail :move) ~
(memberp :input arrowtext :move)
end
;; Display machine state
to accept
display "accept
end
to reject
display "reject
end
to blank
display "| |
end
to display :text
localmake "oldpos cursor
setcursor [15 1]
type :text
setcursor :oldpos
end
;; Data abstraction for machines
to startpart :machine
output first :machine
end
to movepart :machine
output first bf :machine
end
to acceptpart :machine
output last :machine
end
to make.machine :start :moves :accept
output (list :start :moves :accept)
end
;; Data abstraction for arrows
to arrowtail :arrow
output first :arrow
end
to arrowtext :arrow
output first butfirst :arrow
end
to arrowhead :arrow
output last :arrow
end
to make.arrow :tail :text :head
output (list :tail :text :head)
end
;; Machine descriptions for the guessing game
make "mach1 [1 [[1 AB 1]] [1]]
make "mach2 [1 [[1 ABC 2] [2 ABC 1]] [1]]
make "mach3 [1 [[1 A 2] [2 B 3] [3 ABC 3]] [3]]
make "mach4 [1 [[1 A 2] [1 B 3] [1 C 4] [2 A 1] [3 B 1] [4 C 1]] [1]]
make "mach5 [1 [[1 ABC 2] [2 B 1]] [1]]
make "mach6 [1 [[1 A 2] [2 AB 2] [2 C 3] [3 AB 2] [3 C 3]] [3]]
make "mach7 [1 [[1 AB 1] [1 C 2] [2 C 1]] [1]]
make "mach8 [1 [[1 A 2] [1 BC 1] [2 A 1] [2 BC 2]] [1]]
make "mach9 [1 [[1 AB 1] [1 C 2] [2 A 3] [2 B 1] [3 A 1]] [1]]
make "mach10 [1 [[1 A 2] [1 BC 1] [2 A 2] [2 B 3] [2 C 1]
[3 A 2] [3 B 1] [3 C 4] [4 A 2] [4 B 5] [4 C 1]
[5 A 6] [5 BC 1] [6 ABC 6]]
[6]]
;;; Regular Expression to FSM Translation (<A NAME="machine">MACHINE</A>)
to machine :regexp
localmake "nextstate 0
output optimize determine nondet :regexp
end
;; First step: make a possibly <A NAME="nondet">nondeterministic</A> machine
to nondet :regexp
if and (wordp :regexp) (equalp count :regexp 1) ~
[output ndletter :regexp]
if wordp :regexp [output ndor reduce "sentence :regexp]
if equalp first :regexp "or [output ndor butfirst :regexp]
if equalp first :regexp "* [output ndmany last :regexp]
output ndconcat :regexp
end
;; <A NAME="ndletter">Alphabet</A> rule
to ndletter :letter
localmake "from newstate
localmake "to newstate
output (make.machine :from
(list (make.arrow :from :letter :to))
(list :to))
end
;; <A NAME="ndconcat">Concatenation</A> rule
to ndconcat :exprs
output reduce "string (map "nondet :exprs)
end
to string :machine1 :machine2
output (make.machine (startpart :machine1)
(sentence (movepart :machine1)
(splice acceptpart :machine1 :machine2)
(movepart :machine2))
(stringa (acceptpart :machine1)
(startpart :machine2)
(acceptpart :machine2)))
end
to stringa :accept1 :start2 :accept2
if memberp :start2 :accept2 [output sentence :accept1 :accept2]
output :accept2
end
;; <A NAME="ndor">Alternatives</A> rule
to ndor :exprs
localmake "newstart newstate
localmake "machines (map "nondet :exprs)
localmake "accepts map.se "acceptpart :machines
output (make.machine :newstart
(sentence map.se "movepart :machines
map.se "or.splice :machines)
ifelse not emptyp find [memberp (startpart ?)
(acceptpart ?)]
:machines
[fput :newstart :accepts]
[:accepts])
end
to or.splice :machine
output map [newtail ? :newstart] (arrows.from.start :machine)
end
;; <A NAME="ndmany">Repetition</A> rule
to ndmany :regexp
localmake "machine nondet :regexp
output (make.machine (startpart :machine)
sentence (movepart :machine)
(splice (acceptpart :machine) :machine)
fput (startpart :machine) (acceptpart :machine))
end
;; <A NAME="splice">Generate</A> moves from a bunch of given states (:accepts) duplicating
;; the moves from the start state of some machine (:machine).
;; Used for concatenation rule to splice two formerly separate machines;
;; used for repetition rule to "splice" a machine to itself.
to splice :accepts :machine
output map.se [copy.to.accepts ?] (arrows.from.start :machine)
end
to arrows.from.start :machine
output filter [equalp startpart :machine arrowtail ?] movepart :machine
end
to copy.to.accepts :move
output map [newtail :move ?] :accepts
end
to newtail :arrow :tail
output make.arrow :tail (arrowtext :arrow) (arrowhead :arrow)
end
;; <A NAME="newstate">Make</A> a new state number
to newstate
make "nextstate :nextstate+1
output :nextstate
end
;; Second step: Turn nondeterministic FSM into a <A NAME="determine">deterministic</A> one
;; Also eliminates "orphan" (unreachable) states.
to determine :machine
localmake "moves movepart :machine
localmake "accepts acceptpart :machine
localmake "states []
localmake "join.state.list []
localmake "newmoves nd.traverse (startpart :machine)
output make.machine (startpart :machine) ~
:newmoves ~
filter [memberp ? :states] :accepts
end
to <A NAME="nd.traverse">nd.traverse</A> :state
if memberp :state :states [output []]
make "states fput :state :states
localmake "newmoves (check.nd filter [equalp arrowtail ? :state] :moves)
output sentence :newmoves map.se "nd.traverse (map "arrowhead :newmoves)
end
to <A NAME="check.nd">check.nd</A> :movelist
if emptyp :movelist [output []]
localmake "letter arrowtext first :movelist
localmake "heads sort map "arrowhead ~
filter [equalp :letter arrowtext ?] :movelist
if emptyp butfirst :heads ~
[output fput first :movelist
check.nd filter [not equalp :letter arrowtext ?]
:movelist]
localmake "check.heads member :heads :join.state.list
if not emptyp :check.heads ~
[output fput make.arrow :state :letter first butfirst :check.heads ~
check.nd filter [not equalp :letter arrowtext ?]
:movelist]
localmake "join.state newstate
make "join.state.list fput :heads fput :join.state :join.state.list
make "moves sentence :moves ~
map [make.arrow :join.state
arrowtext ?
arrowhead ?] ~
filter [memberp arrowtail ? :heads] :moves
if not emptyp find [memberp ? :accepts] :heads ~
[make "accepts sentence :accepts :join.state]
output fput make.arrow :state :letter :join.state ~
check.nd filter [not equalp :letter arrowtext ?] :movelist
end
to sort :list
if emptyp :list [output []]
output insert first :list sort butfirst :list
end
to insert :value :sorted
if emptyp :sorted [output (list :value)]
if :value = first :sorted [output :sorted]
if :value < first :sorted [output fput :value :sorted]
output fput first :sorted insert :value butfirst :sorted
end
;; Third step: <A NAME="optimize">Combine</A> redundant states.
;; Also combines arrows with same head and tail:
;; [1 A 2] [1 B 2] -> [1 AB 2].
to optimize :machine
localmake "stubarray array :nextstate
foreach (movepart :machine) "array.save
localmake "states sort fput (startpart :machine) ~
map "arrowhead movepart :machine
localmake "start startpart :machine
foreach reverse :states [optimize.state ? ?rest]
output (make.machine :start
map.se [fix.arrows ? item ? :stubarray] :states
filter [memberp ? :states] acceptpart :machine)
end
to array.save :move
setitem (arrowtail :move) :stubarray ~
stub.add (arrow.stub :move) (item (arrowtail :move) :stubarray)
end
to <A NAME="stub.add">stub.add</A> :stub :stublist
if emptyp :stublist [output (list :stub)]
if (stub.head :stub) < (stub.head first :stublist) ~
[output fput :stub :stublist]
if (stub.head :stub) = (stub.head first :stublist) ~
[output fput make.stub letter.join (stub.text :stub)
(stub.text first :stublist)
stub.head :stub
butfirst :stublist]
output fput first :stublist (stub.add :stub butfirst :stublist)
end
to letter.join :this :those
if emptyp :those [output :this]
if beforep :this first :those [output word :this :those]
output word (first :those) (letter.join :this butfirst :those)
end
to optimize.state :state :others
localmake "candidates ~
filter (ifelse memberp :state acceptpart :machine
[[memberp ? acceptpart :machine]]
[[not memberp ? acceptpart :machine]]) ~
:others
localmake "mymoves item :state :stubarray
localmake "twin find [equalp (item ? :stubarray) :mymoves] :candidates
if emptyp :twin [stop]
make "states remove :state :states
if equalp :start :state [make "start :twin]
foreach :states ~
[setitem ? :stubarray
(cascade [emptyp ?2]
[stub.add (change.head :state :twin first ?2)
?1]
filter [not equalp stub.head ? :state]
item ? :stubarray
[butfirst ?2]
filter [equalp stub.head ? :state]
item ? :stubarray)]
end
to change.head :from :to :stub
if not equalp (stub.head :stub) :from [output :stub]
output list (stub.text :stub) :to
end
to fix.arrows :state :stublist
output map [stub.arrow :state ?] :stublist
end
;; Data abstraction for "stub" arrow (no tail)
to arrow.stub :arrow
output butfirst :arrow
end
to make.stub :text :head
output list :text :head
end
to stub.text :stub
output first :stub
end
to stub.head :stub
output last :stub
end
to stub.arrow :tail :stub
output fput :tail :stub
end
</PRE><P>
<P><A HREF="../v3-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v3ch0/v3ch0.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v3ch2/v3ch2.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|