754:
The reverse construction is also possible. Given some Turing machine, it is possible to create an equivalent unrestricted grammar which even uses only productions with one or more non-terminal symbols on their left-hand sides. Therefore, an arbitrary unrestricted grammar can always be equivalently
829:
The equivalence of unrestricted grammars to Turing machines implies the existence of a universal unrestricted grammar, a grammar capable of accepting any other unrestricted grammar's language given a description of the language. For this reason, it is theoretically possible to build a
1163:
791:
can be generated by a given unrestricted grammar is equivalent to the problem of whether it can be accepted by the Turing machine equivalent to the grammar. The latter problem is called the
698:
Compare the resulting sentential form on tape 2 to the word on tape 1. If they match, then the Turing machine accepts the word. If they don't, the Turing machine will go back to step 1.
1206:
898:
265:
530:
43:. No restrictions are made on the productions of an unrestricted grammar, other than each of their left-hand sides being non-empty. This grammar class can generate arbitrary
900:
is not strictly necessary since unrestricted grammars make no real distinction between the two. The designation exists purely so that one knows when to stop generating
110:
693:
653:
613:
351:
331:
285:
673:
633:
593:
573:
381:
305:
931:
749:
446:
1124:
1104:
1084:
1064:
1044:
1020:
1000:
980:
951:
789:
720:
550:
494:
470:
413:
232:
207:
187:
163:
133:
1526:
1199:
1413:
1192:
1022:
explicitly, the proof of their
Theorem 9.3 (construction of an equivalent Turing machine from a given unrestricted grammar, p.221, cf. Section
395:
The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar
1338:
755:
converted to obey the latter form, by converting it to a Turing machine and back again. Some authors use the latter form as definition of
1428:
1353:
1172:
1521:
1506:
1382:
823:
449:
44:
387:
As the name implies, there are no real restrictions on the types of production rules that unrestricted grammars can have.
235:
1399:
1324:
1496:
500:
Start at the left of the second tape and repeatedly choose to move right or select the current position on the tape.
1392:
503:
448:
and vice versa. Given an unrestricted grammar, such a Turing machine is simple enough to construct, as a two-tape
1568:
1317:
815:
1469:
1464:
1550:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
615:
at that point, possibly shifting the symbols on the tape left or right depending on the relative lengths of
1480:
1418:
1343:
1423:
1371:
1184:
871:
799:
241:
509:
1516:
1491:
1348:
831:
722:
on its second tape after the last step is executed an arbitrary number of times, thus the language
1501:
1443:
1387:
811:
140:
1236:
1168:
702:
It is easy to see that this Turing machine will generate all and only the sentential forms of
40:
678:
638:
598:
336:
310:
270:
65:
1485:
1438:
1405:
1251:
848:
768:
658:
618:
578:
558:
360:
290:
1448:
1363:
1330:
1246:
1219:
1215:
907:
843:
792:
725:
473:
422:
166:
20:
1459:
1241:
1223:
1158:
1109:
1089:
1069:
1049:
1029:
1005:
985:
965:
936:
901:
819:
774:
705:
535:
479:
455:
416:
398:
217:
192:
172:
148:
118:
60:
1562:
1544:
1154:
807:
209:
851:– doesn't distinguish terminal and nonterminal symbols, admits empty left-hand sides
1511:
1433:
1358:
803:
136:
962:
While
Hopcroft and Ullman (1979) do not mention the cardinalities of
472:
to be tested, and the second tape is used by the machine to generate
1474:
1188:
1543:
Each category of languages, except those marked by a , is a
1164:
Introduction to
Automata Theory, Languages, and Computation
1126:
can be omitted without affecting the generated language.
1149:
1147:
1145:
1143:
68:
1112:
1092:
1072:
1052:
1032:
1008:
988:
968:
939:
910:
874:
777:
728:
708:
681:
661:
641:
621:
601:
581:
575:
appears at some position on the second tape, replace
561:
538:
512:
482:
458:
425:
401:
363:
339:
313:
293:
273:
244:
220:
195:
175:
151:
121:
1023:
1118:
1098:
1078:
1058:
1038:
1014:
994:
974:
945:
925:
892:
824:Recursively enumerable language#Closure properties
783:
743:
714:
687:
667:
647:
627:
607:
587:
567:
544:
524:
488:
464:
440:
407:
375:
345:
325:
299:
279:
259:
226:
201:
181:
157:
127:
104:
496:. The Turing machine then does the following:
39:) is the most general class of grammars in the
1046:and finite lengths of all strings in rules of
1200:
953:is restricted to strings of terminal symbols.
904:of the grammar; more precisely, the language
8:
834:based on unrestricted grammars (e.g. Thue).
1522:Counter-free (with aperiodic finite monoid)
1232:
1207:
1193:
1185:
452:. The first tape contains the input word
1111:
1091:
1071:
1051:
1031:
1007:
987:
967:
938:
909:
873:
776:
727:
707:
680:
660:
640:
620:
600:
580:
560:
537:
511:
481:
457:
424:
400:
362:
338:
312:
292:
272:
243:
219:
194:
174:
150:
120:
67:
1139:
861:
383:is a specially designated start symbol.
1414:Linear context-free rewriting language
1339:Linear context-free rewriting systems
798:Recursively enumerable languages are
7:
1547:of the category directly above it.
893:{\displaystyle T\cap N=\emptyset }
887:
260:{\displaystyle \alpha \to \beta ,}
14:
1026:) tacitly requires finiteness of
525:{\displaystyle \beta \to \gamma }
1167:(1st ed.). Addison-Wesley.
751:must be recursively enumerable.
45:recursively enumerable languages
1024:#Equivalence to Turing machines
695:, shift the tape symbols left).
450:nondeterministic Turing machine
920:
914:
738:
732:
516:
435:
429:
391:Equivalence to Turing machines
248:
99:
75:
1:
353:is not the empty string, and
1585:
1429:Deterministic context-free
1354:Deterministic context-free
771:of whether a given string
307:are strings of symbols in
1540:
1502:Nondeterministic pushdown
1230:
37:phrase structure grammars
763:Computational properties
532:from the productions in
105:{\textstyle G=(N,T,P,S)}
1106:that does not occur in
688:{\displaystyle \gamma }
648:{\displaystyle \gamma }
608:{\displaystyle \gamma }
419:capable of recognizing
346:{\displaystyle \alpha }
326:{\displaystyle N\cup T}
280:{\displaystyle \alpha }
1507:Deterministic pushdown
1383:Recursively enumerable
1120:
1100:
1080:
1060:
1040:
1016:
996:
976:
947:
927:
894:
785:
745:
716:
689:
669:
668:{\displaystyle \beta }
649:
629:
628:{\displaystyle \beta }
609:
589:
588:{\displaystyle \beta }
569:
568:{\displaystyle \beta }
546:
526:
490:
466:
442:
409:
377:
376:{\displaystyle S\in N}
347:
327:
301:
300:{\displaystyle \beta }
281:
261:
228:
203:
183:
159:
129:
106:
1121:
1101:
1081:
1061:
1041:
1017:
997:
977:
948:
928:
895:
786:
746:
717:
690:
670:
650:
630:
610:
590:
570:
547:
527:
491:
467:
443:
410:
378:
348:
328:
302:
282:
262:
229:
204:
184:
160:
130:
107:
25:unrestricted grammars
1492:Tree stack automaton
1110:
1090:
1070:
1050:
1030:
1006:
986:
966:
937:
926:{\displaystyle L(G)}
908:
872:
832:programming language
795:and is undecidable.
775:
757:unrestricted grammar
744:{\displaystyle L(G)}
726:
706:
679:
659:
639:
619:
599:
579:
559:
536:
510:
506:choose a production
504:Nondeterministically
480:
456:
441:{\displaystyle L(G)}
423:
399:
361:
337:
311:
291:
271:
242:
218:
193:
173:
149:
119:
66:
57:unrestricted grammar
1400:range concatenation
1325:range concatenation
234:is a finite set of
165:is a finite set of
141:nonterminal symbols
1159:Ullman, Jeffrey D.
1116:
1096:
1076:
1056:
1036:
1012:
992:
972:
943:
923:
890:
781:
741:
712:
685:
665:
645:
625:
605:
585:
565:
542:
522:
486:
462:
438:
415:there exists some
405:
373:
343:
323:
297:
277:
257:
224:
199:
179:
155:
125:
102:
1556:
1555:
1535:
1534:
1497:Embedded pushdown
1393:Context-sensitive
1318:Context-sensitive
1252:Abstract machines
1237:Chomsky hierarchy
1119:{\displaystyle P}
1099:{\displaystyle T}
1079:{\displaystyle N}
1059:{\displaystyle P}
1039:{\displaystyle P}
1015:{\displaystyle P}
995:{\displaystyle T}
975:{\displaystyle N}
946:{\displaystyle G}
784:{\displaystyle s}
715:{\displaystyle G}
545:{\displaystyle G}
489:{\displaystyle G}
465:{\displaystyle w}
408:{\displaystyle G}
227:{\displaystyle P}
202:{\displaystyle T}
182:{\displaystyle N}
158:{\displaystyle T}
128:{\displaystyle N}
51:Formal definition
41:Chomsky hierarchy
1576:
1569:Formal languages
1551:
1548:
1512:Visibly pushdown
1486:Thread automaton
1434:Visibly pushdown
1402:
1359:Visibly pushdown
1327:
1314:(no common name)
1233:
1220:formal languages
1209:
1202:
1195:
1186:
1179:
1178:
1151:
1127:
1125:
1123:
1122:
1117:
1105:
1103:
1102:
1097:
1085:
1083:
1082:
1077:
1066:. Any member of
1065:
1063:
1062:
1057:
1045:
1043:
1042:
1037:
1021:
1019:
1018:
1013:
1001:
999:
998:
993:
981:
979:
978:
973:
960:
954:
952:
950:
949:
944:
932:
930:
929:
924:
902:sentential forms
899:
897:
896:
891:
866:
849:Semi-Thue system
818:, but not under
790:
788:
787:
782:
769:decision problem
750:
748:
747:
742:
721:
719:
718:
713:
694:
692:
691:
686:
674:
672:
671:
666:
654:
652:
651:
646:
634:
632:
631:
626:
614:
612:
611:
606:
594:
592:
591:
586:
574:
572:
571:
566:
551:
549:
548:
543:
531:
529:
528:
523:
495:
493:
492:
487:
474:sentential forms
471:
469:
468:
463:
447:
445:
444:
439:
414:
412:
411:
406:
382:
380:
379:
374:
352:
350:
349:
344:
332:
330:
329:
324:
306:
304:
303:
298:
286:
284:
283:
278:
266:
264:
263:
258:
236:production rules
233:
231:
230:
225:
208:
206:
205:
200:
188:
186:
185:
180:
167:terminal symbols
164:
162:
161:
156:
134:
132:
131:
126:
111:
109:
108:
103:
1584:
1583:
1579:
1578:
1577:
1575:
1574:
1573:
1559:
1558:
1557:
1552:
1549:
1542:
1536:
1531:
1453:
1397:
1376:
1322:
1303:
1226:
1224:formal grammars
1216:Automata theory
1213:
1183:
1182:
1175:
1153:
1152:
1141:
1136:
1131:
1130:
1108:
1107:
1088:
1087:
1068:
1067:
1048:
1047:
1028:
1027:
1004:
1003:
984:
983:
964:
963:
961:
957:
935:
934:
906:
905:
870:
869:
867:
863:
858:
844:Lambda calculus
840:
793:halting problem
773:
772:
765:
724:
723:
704:
703:
677:
676:
675:is longer than
657:
656:
637:
636:
617:
616:
597:
596:
577:
576:
557:
556:
534:
533:
508:
507:
478:
477:
454:
453:
421:
420:
397:
396:
393:
359:
358:
335:
334:
309:
308:
289:
288:
269:
268:
240:
239:
216:
215:
191:
190:
171:
170:
147:
146:
117:
116:
64:
63:
53:
23:, the class of
21:automata theory
17:
16:Language Theory
12:
11:
5:
1582:
1580:
1572:
1571:
1561:
1560:
1554:
1553:
1541:
1538:
1537:
1533:
1532:
1530:
1529:
1527:Acyclic finite
1524:
1519:
1514:
1509:
1504:
1499:
1494:
1488:
1483:
1478:
1477:Turing Machine
1472:
1470:Linear-bounded
1467:
1462:
1460:Turing machine
1456:
1454:
1452:
1451:
1446:
1441:
1436:
1431:
1426:
1421:
1419:Tree-adjoining
1416:
1411:
1408:
1403:
1395:
1390:
1385:
1379:
1377:
1375:
1374:
1369:
1366:
1361:
1356:
1351:
1346:
1344:Tree-adjoining
1341:
1336:
1333:
1328:
1320:
1315:
1312:
1306:
1304:
1302:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1258:
1255:
1254:
1249:
1244:
1239:
1231:
1228:
1227:
1214:
1212:
1211:
1204:
1197:
1189:
1181:
1180:
1173:
1155:Hopcroft, John
1138:
1137:
1135:
1132:
1129:
1128:
1115:
1095:
1075:
1055:
1035:
1011:
991:
971:
955:
942:
933:recognized by
922:
919:
916:
913:
889:
886:
883:
880:
877:
860:
859:
857:
854:
853:
852:
846:
839:
836:
820:set difference
780:
764:
761:
740:
737:
734:
731:
711:
700:
699:
696:
684:
664:
644:
624:
604:
584:
564:
553:
541:
521:
518:
515:
501:
485:
461:
437:
434:
431:
428:
417:Turing machine
404:
392:
389:
385:
384:
372:
369:
366:
355:
354:
342:
322:
319:
316:
296:
276:
256:
253:
250:
247:
223:
213:
198:
178:
154:
144:
124:
101:
98:
95:
92:
89:
86:
83:
80:
77:
74:
71:
61:formal grammar
52:
49:
15:
13:
10:
9:
6:
4:
3:
2:
1581:
1570:
1567:
1566:
1564:
1546:
1545:proper subset
1539:
1528:
1525:
1523:
1520:
1518:
1515:
1513:
1510:
1508:
1505:
1503:
1500:
1498:
1495:
1493:
1489:
1487:
1484:
1482:
1479:
1476:
1473:
1471:
1468:
1466:
1463:
1461:
1458:
1457:
1455:
1450:
1447:
1445:
1442:
1440:
1437:
1435:
1432:
1430:
1427:
1425:
1422:
1420:
1417:
1415:
1412:
1409:
1407:
1404:
1401:
1396:
1394:
1391:
1389:
1386:
1384:
1381:
1380:
1378:
1373:
1372:Non-recursive
1370:
1367:
1365:
1362:
1360:
1357:
1355:
1352:
1350:
1347:
1345:
1342:
1340:
1337:
1334:
1332:
1329:
1326:
1321:
1319:
1316:
1313:
1311:
1308:
1307:
1305:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1259:
1257:
1256:
1253:
1250:
1248:
1245:
1243:
1240:
1238:
1235:
1234:
1229:
1225:
1221:
1217:
1210:
1205:
1203:
1198:
1196:
1191:
1190:
1187:
1176:
1174:0-201-44124-1
1170:
1166:
1165:
1160:
1156:
1150:
1148:
1146:
1144:
1140:
1133:
1113:
1093:
1073:
1053:
1033:
1025:
1009:
989:
969:
959:
956:
940:
917:
911:
903:
884:
881:
878:
875:
865:
862:
855:
850:
847:
845:
842:
841:
837:
835:
833:
827:
825:
821:
817:
813:
809:
808:concatenation
805:
801:
796:
794:
778:
770:
762:
760:
758:
752:
735:
729:
709:
697:
682:
662:
642:
622:
602:
582:
562:
554:
539:
519:
513:
505:
502:
499:
498:
497:
483:
475:
459:
451:
432:
426:
418:
402:
390:
388:
370:
367:
364:
357:
356:
340:
320:
317:
314:
294:
274:
254:
251:
245:
237:
221:
214:
211:
196:
176:
168:
152:
145:
142:
138:
122:
115:
114:
113:
96:
93:
90:
87:
84:
81:
78:
72:
69:
62:
58:
50:
48:
46:
42:
38:
34:
30:
27:(also called
26:
22:
1481:Nested stack
1424:Context-free
1349:Context-free
1310:Unrestricted
1309:
1162:
958:
864:
828:
816:intersection
797:
766:
756:
753:
701:
394:
386:
238:of the form
56:
54:
36:
32:
28:
24:
18:
1490:restricted
804:Kleene star
1134:References
868:Actually,
137:finite set
1444:Star-free
1398:Positive
1388:Decidable
1323:Positive
1247:Languages
888:∅
879:∩
683:γ
663:β
655:(e.g. if
643:γ
623:β
603:γ
583:β
563:β
520:γ
517:→
514:β
368:∈
341:α
318:∪
295:β
275:α
252:β
249:→
246:α
29:semi-Thue
1563:Category
1242:Grammars
1161:(1979).
838:See also
210:disjoint
112:, where
1465:Decider
1439:Regular
1406:Indexed
1364:Regular
1331:Indexed
1517:Finite
1449:Finite
1294:Type-3
1285:Type-2
1267:Type-1
1261:Type-0
1171:
822:; see
814:, and
802:under
800:closed
267:where
33:type-0
1475:PTIME
856:Notes
812:union
476:from
169:with
135:is a
59:is a
1222:and
1169:ISBN
767:The
635:and
333:and
287:and
189:and
1086:or
595:by
555:If
139:of
55:An
35:or
19:In
1565::
1218::
1157:;
1142:^
1002:,
982:,
826:.
810:,
806:,
759:.
47:.
31:,
1410:—
1368:—
1335:—
1300:—
1297:—
1291:—
1288:—
1282:—
1279:—
1276:—
1273:—
1270:—
1264:—
1208:e
1201:t
1194:v
1177:.
1114:P
1094:T
1074:N
1054:P
1034:P
1010:P
990:T
970:N
941:G
921:)
918:G
915:(
912:L
885:=
882:N
876:T
779:s
739:)
736:G
733:(
730:L
710:G
552:.
540:G
484:G
460:w
436:)
433:G
430:(
427:L
403:G
371:N
365:S
321:T
315:N
255:,
222:P
212:,
197:T
177:N
153:T
143:,
123:N
100:)
97:S
94:,
91:P
88:,
85:T
82:,
79:N
76:(
73:=
70:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.