165:
1377:
63:
22:
452:
1015:
572:
760:
512:
807:
342:
388:
986:
935:
683:
646:
609:
310:
899:
194:
867:
847:
827:
703:
362:
284:
1335:
1008:
260:
1418:
1222:
1001:
1147:
1237:
946:
1162:
35:
234:
216:
146:
49:
1330:
1315:
127:
1191:
99:
84:
77:
872:
The first application of the interchange lemma was to show that the set of repetitive strings (i.e., strings of the form
106:
1208:
1133:
393:
1305:
1411:
1201:
113:
1437:
1126:
959:
William Ogden, Rockford J. Ross, and Karl
Winklmann (1982). "An "Interchange Lemma" for Context-Free Languages".
177:
1278:
1273:
187:
181:
173:
95:
1359:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
73:
517:
1447:
1289:
1227:
1152:
708:
256:
198:
41:
1404:
1232:
1180:
993:
980:
457:
1325:
1300:
1157:
1118:
765:
315:
1310:
1252:
1196:
367:
120:
1045:
904:
651:
614:
577:
1294:
1247:
1214:
1060:
968:
289:
1442:
1257:
1172:
1139:
1055:
1028:
1024:
875:
248:
1388:
1268:
1050:
1032:
852:
832:
812:
688:
347:
269:
1431:
1353:
1320:
1242:
1167:
62:
1376:
1384:
972:
937:) over an alphabet of three or more characters is not context-free.
1283:
997:
158:
56:
15:
1352:
Each category of languages, except those marked by a , is a
1392:
907:
878:
855:
835:
815:
768:
711:
691:
654:
617:
580:
520:
460:
396:
370:
350:
318:
292:
272:
929:
893:
861:
841:
821:
801:
754:
697:
677:
640:
603:
566:
506:
447:{\displaystyle Z=\{z_{1},\ldots ,z_{k}\}\subset R}
446:
382:
356:
336:
304:
278:
255:states a necessary condition for a language to be
186:but its sources remain unclear because it lacks
266:It states that for every context-free language
1412:
1009:
8:
985:: CS1 maint: multiple names: authors list (
435:
403:
1331:Counter-free (with aperiodic finite monoid)
50:Learn how and when to remove these messages
1419:
1405:
1041:
1016:
1002:
994:
916:
908:
906:
877:
854:
834:
814:
793:
783:
773:
767:
741:
735:
726:
715:
710:
690:
670:
664:
655:
653:
633:
627:
618:
616:
596:
590:
581:
579:
558:
548:
538:
525:
519:
495:
480:
475:
467:
459:
429:
410:
395:
369:
349:
317:
291:
271:
235:Learn how and when to remove this message
217:Learn how and when to remove this message
147:Learn how and when to remove this message
261:pumping lemma for context-free languages
1223:Linear context-free rewriting language
978:
83:Please improve this article by adding
1148:Linear context-free rewriting systems
567:{\displaystyle z_{i}=w_{i}x_{i}y_{i}}
7:
1373:
1371:
755:{\displaystyle m/2<|x_{i}|\leq m}
947:Pumping lemma for regular languages
1356:of the category directly above it.
507:{\displaystyle k\geq |R|/(cn^{2})}
14:
31:This article has multiple issues.
1375:
163:
61:
20:
802:{\displaystyle w_{i}x_{j}y_{i}}
39:or discuss these issues on the
917:
909:
742:
727:
671:
656:
634:
619:
597:
582:
501:
485:
476:
468:
1:
344:for any collection of length
337:{\displaystyle n\geq m\geq 2}
85:secondary or tertiary sources
1391:. You can help Knowledge by
1464:
1370:
1238:Deterministic context-free
1163:Deterministic context-free
383:{\displaystyle R\subset L}
1349:
1311:Nondeterministic pushdown
1039:
961:SIAM Journal on Computing
930:{\displaystyle |y|>0}
172:This article includes a
678:{\displaystyle |y_{i}|}
641:{\displaystyle |x_{i}|}
604:{\displaystyle |w_{i}|}
201:more precise citations.
1387:-related article is a
1316:Deterministic pushdown
1192:Recursively enumerable
931:
895:
863:
843:
823:
803:
756:
699:
679:
642:
605:
568:
508:
448:
384:
358:
338:
306:
305:{\displaystyle c>0}
280:
72:relies excessively on
932:
896:
864:
844:
824:
804:
757:
700:
680:
643:
606:
569:
514:, and decompositions
509:
449:
385:
359:
339:
307:
281:
1301:Tree stack automaton
905:
894:{\displaystyle xyyz}
876:
853:
833:
813:
766:
709:
689:
652:
615:
578:
518:
458:
394:
368:
348:
316:
290:
270:
1209:range concatenation
1134:range concatenation
96:"Interchange lemma"
927:
891:
859:
839:
819:
799:
752:
695:
685:is independent of
675:
638:
601:
574:such that each of
564:
504:
444:
380:
354:
334:
312:such that for all
302:
276:
174:list of references
1400:
1399:
1365:
1364:
1344:
1343:
1306:Embedded pushdown
1202:Context-sensitive
1127:Context-sensitive
1061:Abstract machines
1046:Chomsky hierarchy
862:{\displaystyle j}
842:{\displaystyle i}
822:{\displaystyle L}
698:{\displaystyle i}
357:{\displaystyle n}
279:{\displaystyle L}
253:interchange lemma
247:In the theory of
245:
244:
237:
227:
226:
219:
157:
156:
149:
131:
54:
1455:
1438:Formal languages
1421:
1414:
1407:
1379:
1372:
1360:
1357:
1321:Visibly pushdown
1295:Thread automaton
1243:Visibly pushdown
1211:
1168:Visibly pushdown
1136:
1123:(no common name)
1042:
1029:formal languages
1018:
1011:
1004:
995:
990:
984:
976:
936:
934:
933:
928:
920:
912:
900:
898:
897:
892:
868:
866:
865:
860:
848:
846:
845:
840:
828:
826:
825:
820:
808:
806:
805:
800:
798:
797:
788:
787:
778:
777:
762:, and the words
761:
759:
758:
753:
745:
740:
739:
730:
719:
704:
702:
701:
696:
684:
682:
681:
676:
674:
669:
668:
659:
647:
645:
644:
639:
637:
632:
631:
622:
610:
608:
607:
602:
600:
595:
594:
585:
573:
571:
570:
565:
563:
562:
553:
552:
543:
542:
530:
529:
513:
511:
510:
505:
500:
499:
484:
479:
471:
453:
451:
450:
445:
434:
433:
415:
414:
389:
387:
386:
381:
363:
361:
360:
355:
343:
341:
340:
335:
311:
309:
308:
303:
285:
283:
282:
277:
259:, just like the
249:formal languages
240:
233:
222:
215:
211:
208:
202:
197:this article by
188:inline citations
167:
166:
159:
152:
145:
141:
138:
132:
130:
89:
65:
57:
46:
24:
23:
16:
1463:
1462:
1458:
1457:
1456:
1454:
1453:
1452:
1428:
1427:
1426:
1425:
1368:
1366:
1361:
1358:
1351:
1345:
1340:
1262:
1206:
1185:
1131:
1112:
1035:
1033:formal grammars
1025:Automata theory
1022:
977:
973:10.1137/0214031
958:
955:
943:
903:
902:
874:
873:
851:
850:
831:
830:
811:
810:
789:
779:
769:
764:
763:
731:
707:
706:
687:
686:
660:
650:
649:
623:
613:
612:
586:
576:
575:
554:
544:
534:
521:
516:
515:
491:
456:
455:
425:
406:
392:
391:
366:
365:
346:
345:
314:
313:
288:
287:
268:
267:
241:
230:
229:
228:
223:
212:
206:
203:
192:
178:related reading
168:
164:
153:
142:
136:
133:
90:
88:
82:
78:primary sources
66:
25:
21:
12:
11:
5:
1461:
1459:
1451:
1450:
1445:
1440:
1430:
1429:
1424:
1423:
1416:
1409:
1401:
1398:
1397:
1380:
1363:
1362:
1350:
1347:
1346:
1342:
1341:
1339:
1338:
1336:Acyclic finite
1333:
1328:
1323:
1318:
1313:
1308:
1303:
1297:
1292:
1287:
1286:Turing Machine
1281:
1279:Linear-bounded
1276:
1271:
1269:Turing machine
1265:
1263:
1261:
1260:
1255:
1250:
1245:
1240:
1235:
1230:
1228:Tree-adjoining
1225:
1220:
1217:
1212:
1204:
1199:
1194:
1188:
1186:
1184:
1183:
1178:
1175:
1170:
1165:
1160:
1155:
1153:Tree-adjoining
1150:
1145:
1142:
1137:
1129:
1124:
1121:
1115:
1113:
1111:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1067:
1064:
1063:
1058:
1053:
1048:
1040:
1037:
1036:
1023:
1021:
1020:
1013:
1006:
998:
992:
991:
967:(2): 410–415.
954:
951:
950:
949:
942:
939:
926:
923:
919:
915:
911:
890:
887:
884:
881:
858:
838:
818:
796:
792:
786:
782:
776:
772:
751:
748:
744:
738:
734:
729:
725:
722:
718:
714:
694:
673:
667:
663:
658:
636:
630:
626:
621:
599:
593:
589:
584:
561:
557:
551:
547:
541:
537:
533:
528:
524:
503:
498:
494:
490:
487:
483:
478:
474:
470:
466:
463:
443:
440:
437:
432:
428:
424:
421:
418:
413:
409:
405:
402:
399:
379:
376:
373:
353:
333:
330:
327:
324:
321:
301:
298:
295:
275:
243:
242:
225:
224:
207:September 2022
182:external links
171:
169:
162:
155:
154:
69:
67:
60:
55:
29:
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
1460:
1449:
1448:Grammar stubs
1446:
1444:
1441:
1439:
1436:
1435:
1433:
1422:
1417:
1415:
1410:
1408:
1403:
1402:
1396:
1394:
1390:
1386:
1381:
1378:
1374:
1369:
1355:
1354:proper subset
1348:
1337:
1334:
1332:
1329:
1327:
1324:
1322:
1319:
1317:
1314:
1312:
1309:
1307:
1304:
1302:
1298:
1296:
1293:
1291:
1288:
1285:
1282:
1280:
1277:
1275:
1272:
1270:
1267:
1266:
1264:
1259:
1256:
1254:
1251:
1249:
1246:
1244:
1241:
1239:
1236:
1234:
1231:
1229:
1226:
1224:
1221:
1218:
1216:
1213:
1210:
1205:
1203:
1200:
1198:
1195:
1193:
1190:
1189:
1187:
1182:
1181:Non-recursive
1179:
1176:
1174:
1171:
1169:
1166:
1164:
1161:
1159:
1156:
1154:
1151:
1149:
1146:
1143:
1141:
1138:
1135:
1130:
1128:
1125:
1122:
1120:
1117:
1116:
1114:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1068:
1066:
1065:
1062:
1059:
1057:
1054:
1052:
1049:
1047:
1044:
1043:
1038:
1034:
1030:
1026:
1019:
1014:
1012:
1007:
1005:
1000:
999:
996:
988:
982:
974:
970:
966:
962:
957:
956:
952:
948:
945:
944:
940:
938:
924:
921:
913:
888:
885:
882:
879:
870:
856:
836:
816:
794:
790:
784:
780:
774:
770:
749:
746:
736:
732:
723:
720:
716:
712:
692:
665:
661:
628:
624:
591:
587:
559:
555:
549:
545:
539:
535:
531:
526:
522:
496:
492:
488:
481:
472:
464:
461:
441:
438:
430:
426:
422:
419:
416:
411:
407:
400:
397:
377:
374:
371:
351:
331:
328:
325:
322:
319:
299:
296:
293:
273:
264:
262:
258:
254:
250:
239:
236:
221:
218:
210:
200:
196:
190:
189:
183:
179:
175:
170:
161:
160:
151:
148:
140:
129:
126:
122:
119:
115:
112:
108:
105:
101:
98: –
97:
93:
92:Find sources:
86:
80:
79:
75:
70:This article
68:
64:
59:
58:
53:
51:
44:
43:
38:
37:
32:
27:
18:
17:
1393:expanding it
1382:
1367:
1290:Nested stack
1233:Context-free
1158:Context-free
1119:Unrestricted
981:cite journal
964:
960:
871:
705:, moreover,
265:
257:context-free
252:
246:
231:
213:
204:
193:Please help
185:
143:
134:
124:
117:
110:
103:
91:
71:
47:
40:
34:
33:Please help
30:
1299:restricted
390:there is a
286:there is a
199:introducing
1432:Categories
953:References
829:for every
137:March 2019
107:newspapers
74:references
36:improve it
1253:Star-free
1207:Positive
1197:Decidable
1132:Positive
1056:Languages
747:≤
465:≥
439:⊂
420:…
375:⊂
329:≥
323:≥
42:talk page
1051:Grammars
941:See also
1385:grammar
1274:Decider
1248:Regular
1215:Indexed
1173:Regular
1140:Indexed
809:are in
195:improve
121:scholar
1443:Lemmas
1326:Finite
1258:Finite
1103:Type-3
1094:Type-2
1076:Type-1
1070:Type-0
364:words
251:, the
123:
116:
109:
102:
94:
1383:This
1284:PTIME
901:with
454:with
180:, or
128:JSTOR
114:books
1389:stub
1031:and
987:link
922:>
849:and
724:<
297:>
100:news
969:doi
76:to
1434::
1027::
983:}}
979:{{
965:14
963:.
869:.
648:,
611:,
263:.
184:,
176:,
87:.
45:.
1420:e
1413:t
1406:v
1395:.
1219:—
1177:—
1144:—
1109:—
1106:—
1100:—
1097:—
1091:—
1088:—
1085:—
1082:—
1079:—
1073:—
1017:e
1010:t
1003:v
989:)
975:.
971::
925:0
918:|
914:y
910:|
889:z
886:y
883:y
880:x
857:j
837:i
817:L
795:i
791:y
785:j
781:x
775:i
771:w
750:m
743:|
737:i
733:x
728:|
721:2
717:/
713:m
693:i
672:|
666:i
662:y
657:|
635:|
629:i
625:x
620:|
598:|
592:i
588:w
583:|
560:i
556:y
550:i
546:x
540:i
536:w
532:=
527:i
523:z
502:)
497:2
493:n
489:c
486:(
482:/
477:|
473:R
469:|
462:k
442:R
436:}
431:k
427:z
423:,
417:,
412:1
408:z
404:{
401:=
398:Z
378:L
372:R
352:n
332:2
326:m
320:n
300:0
294:c
274:L
238:)
232:(
220:)
214:(
209:)
205:(
191:.
150:)
144:(
139:)
135:(
125:·
118:·
111:·
104:·
81:.
52:)
48:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
