1078:, and then successively applies the rules (any number of times, in any order) to rewrite this string. This stops when a string containing only terminals is obtained. The language consists of all the strings that can be generated in this manner. Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language. If there are multiple different ways of generating this single string, then the grammar is said to be
50:
751:
1572:
1670:
1064:
1005:
322:
1179:
787:
1210:
861:
909:
627:
647:
432:
1501:
817:
523:
486:
1383:
960:
885:
1351:
1305:
1279:
1466:
1443:
1423:
1403:
1325:
1253:
1233:
1143:
1123:
1103:
933:
607:
583:
563:
543:
460:
408:
380:
17:
658:
67:
114:
1506:
86:
329:
93:
1740:
100:
1767:
1577:
82:
133:
71:
1024:
965:
359:
196:
1018:, the left-hand side of a production must be a single nonterminal symbol. So productions are of the form:
31:
281:
276:
181:
107:
38:
1574:. The language of the grammar is the set of all the strings that can be generated using this process:
1152:
760:
1772:
1186:
315:
301:
286:
150:
912:
826:
60:
894:
612:
261:
632:
1717:
1712:
417:
271:
1471:
796:
502:
465:
1706:
1356:
1074:
To generate a string in the language, one begins with a string consisting of only a single
1015:
938:
870:
496:
8:
1330:
1284:
1258:
296:
211:
1448:
1691:
1428:
1408:
1388:
1310:
1238:
1218:
1128:
1108:
1088:
918:
888:
592:
568:
548:
528:
445:
411:
393:
387:
365:
221:
191:
1737:
1079:
1011:
650:
231:
1762:
649:(rather than leaving the right-hand side blank). So productions are members of the
351:
160:
1744:
1686:
1503:, and are done. We can write this series of choices more briefly, using symbols:
435:
291:
266:
216:
746:{\displaystyle V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}}
1681:
1385:. This process is repeated until we only have symbols from the alphabet (i.e.,
383:
256:
236:
206:
201:
186:
1014:
impose additional restrictions on what constitutes a production. Notably in a
1756:
864:
439:
176:
1701:
586:
355:
820:
362:
performed to generate new symbol sequences. A finite set of productions
1235:, and can choose a rule to apply to it. If we choose rule 1, we replace
1709:(A compact form for writing the productions of a context-free grammar.)
1738:
49:
1696:
1567:{\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}
1747:; Fakultät Informatik der Universität Stuttgart; 1994 (German)
1720:(Emil Post's production systems- a model of computation.)
565:
are arbitrary strings of terminals and nonterminals, and
1580:
1509:
1474:
1451:
1431:
1411:
1391:
1359:
1333:
1313:
1287:
1261:
1241:
1221:
1189:
1155:
1131:
1111:
1091:
1027:
968:
941:
921:
897:
873:
829:
799:
763:
661:
635:
615:
595:
571:
551:
531:
505:
468:
448:
420:
396:
368:
1665:{\displaystyle \{ba,abab,aababb,aaababbb,\dotsc \}}
1007:on the right side of the cartesian product symbol.
609:is the empty string, this is denoted by the symbol
74:. Unsourced material may be challenged and removed.
1664:
1566:
1495:
1460:
1437:
1417:
1397:
1377:
1345:
1319:
1299:
1273:
1247:
1227:
1204:
1173:
1137:
1117:
1097:
1058:
999:
954:
927:
915:. If we do not allow the start symbol to occur in
903:
879:
855:
811:
781:
745:
641:
621:
601:
577:
557:
537:
517:
480:
454:
426:
402:
374:
935:(the word on the right side), we have to replace
1754:
382:is the main component in the specification of a
1085:For example, assume the alphabet consists of
358:specifying a symbol substitution that can be
323:
1659:
1581:
984:
978:
330:
316:
1010:The other types of formal grammar in the
390:). The other components are a finite set
134:Learn how and when to remove this message
1307:. If we choose rule 1 again, we replace
1059:{\displaystyle N\to (N\cup \Sigma )^{*}}
32:Deployment environment § Production
1425:). If we now choose rule 2, we replace
14:
1755:
1000:{\displaystyle (V\setminus \{S\})^{*}}
414:, a finite set (known as an alphabet)
1730:
1069:
72:adding citations to reliable sources
43:
1145:, and we have the following rules:
24:
1043:
776:
718:
421:
83:"Production" computer science
25:
18:Production rule (formal languages)
1784:
975:
714:
197:Semantics (programming languages)
1174:{\displaystyle S\rightarrow aSb}
782:{\displaystyle V:=N\cup \Sigma }
48:
1205:{\displaystyle S\rightarrow ba}
59:needs additional citations for
1543:
1525:
1513:
1193:
1159:
1047:
1034:
1031:
988:
969:
727:
701:
509:
499:, a production is of the form
13:
1:
1724:
27:Method of symbol substitution
7:
1768:Natural language processing
1675:
913:set minus or set difference
856:{\displaystyle V^{*}NV^{*}}
462:and a distinguished symbol
282:Programming language theory
277:Natural language processing
10:
1789:
904:{\displaystyle \setminus }
36:
29:
622:{\displaystyle \epsilon }
302:Automated theorem proving
287:Computational linguistics
1125:, with the start symbol
642:{\displaystyle \lambda }
30:Not to be confused with
427:{\displaystyle \Sigma }
1666:
1568:
1497:
1496:{\displaystyle aababb}
1468:and obtain the string
1462:
1439:
1419:
1399:
1379:
1353:and obtain the string
1347:
1321:
1301:
1281:and obtain the string
1275:
1249:
1229:
1206:
1175:
1139:
1119:
1099:
1060:
1001:
956:
929:
905:
881:
857:
813:
812:{\displaystyle {}^{*}}
783:
747:
643:
623:
603:
579:
559:
539:
519:
518:{\displaystyle u\to v}
482:
481:{\displaystyle S\in N}
456:
428:
404:
376:
262:Propositional calculus
1736:See Klaus Reinhardt:
1718:Post canonical system
1713:Phrase structure rule
1667:
1569:
1498:
1463:
1440:
1420:
1400:
1380:
1378:{\displaystyle aaSbb}
1348:
1322:
1302:
1276:
1250:
1230:
1207:
1176:
1140:
1120:
1100:
1061:
1002:
957:
955:{\displaystyle V^{*}}
930:
906:
882:
880:{\displaystyle \cup }
858:
814:
784:
748:
644:
624:
604:
580:
560:
540:
520:
483:
457:
429:
405:
377:
272:Mathematical notation
1578:
1507:
1472:
1449:
1429:
1409:
1389:
1357:
1331:
1311:
1285:
1259:
1239:
1219:
1187:
1153:
1129:
1109:
1089:
1025:
1016:context-free grammar
966:
939:
919:
895:
871:
827:
797:
761:
659:
633:
613:
593:
569:
549:
529:
503:
497:unrestricted grammar
466:
446:
418:
394:
366:
68:improve this article
37:For other uses, see
1346:{\displaystyle aSb}
1300:{\displaystyle aSb}
1274:{\displaystyle aSb}
1215:then we start with
412:nonterminal symbols
297:Formal verification
212:Well-formed formula
1743:2018-01-17 at the
1692:Generative grammar
1662:
1564:
1493:
1461:{\displaystyle ba}
1458:
1435:
1415:
1395:
1375:
1343:
1317:
1297:
1271:
1245:
1225:
1202:
1171:
1135:
1115:
1095:
1070:Grammar generation
1056:
997:
952:
925:
901:
877:
853:
809:
779:
743:
639:
619:
599:
575:
555:
535:
515:
478:
452:
424:
400:
388:generative grammar
372:
222:Regular expression
1438:{\displaystyle S}
1418:{\displaystyle b}
1398:{\displaystyle a}
1320:{\displaystyle S}
1248:{\displaystyle S}
1228:{\displaystyle S}
1138:{\displaystyle S}
1118:{\displaystyle b}
1098:{\displaystyle a}
1012:Chomsky hierarchy
928:{\displaystyle v}
651:cartesian product
602:{\displaystyle v}
578:{\displaystyle u}
558:{\displaystyle v}
538:{\displaystyle u}
455:{\displaystyle N}
403:{\displaystyle N}
375:{\displaystyle P}
340:
339:
232:Ground expression
192:Semantics (logic)
144:
143:
136:
118:
16:(Redirected from
1780:
1773:Formal languages
1748:
1734:
1707:Backus–Naur form
1671:
1669:
1668:
1663:
1573:
1571:
1570:
1565:
1502:
1500:
1499:
1494:
1467:
1465:
1464:
1459:
1444:
1442:
1441:
1436:
1424:
1422:
1421:
1416:
1404:
1402:
1401:
1396:
1384:
1382:
1381:
1376:
1352:
1350:
1349:
1344:
1326:
1324:
1323:
1318:
1306:
1304:
1303:
1298:
1280:
1278:
1277:
1272:
1254:
1252:
1251:
1246:
1234:
1232:
1231:
1226:
1211:
1209:
1208:
1203:
1180:
1178:
1177:
1172:
1144:
1142:
1141:
1136:
1124:
1122:
1121:
1116:
1104:
1102:
1101:
1096:
1065:
1063:
1062:
1057:
1055:
1054:
1006:
1004:
1003:
998:
996:
995:
961:
959:
958:
953:
951:
950:
934:
932:
931:
926:
910:
908:
907:
902:
886:
884:
883:
878:
862:
860:
859:
854:
852:
851:
839:
838:
818:
816:
815:
810:
808:
807:
802:
788:
786:
785:
780:
752:
750:
749:
744:
742:
741:
726:
725:
713:
712:
697:
696:
684:
683:
671:
670:
648:
646:
645:
640:
628:
626:
625:
620:
608:
606:
605:
600:
584:
582:
581:
576:
564:
562:
561:
556:
544:
542:
541:
536:
524:
522:
521:
516:
487:
485:
484:
479:
461:
459:
458:
453:
436:terminal symbols
433:
431:
430:
425:
409:
407:
406:
401:
386:(specifically a
381:
379:
378:
373:
352:computer science
332:
325:
318:
161:Formal languages
146:
145:
139:
132:
128:
125:
119:
117:
76:
52:
44:
21:
1788:
1787:
1783:
1782:
1781:
1779:
1778:
1777:
1753:
1752:
1751:
1745:Wayback Machine
1735:
1731:
1727:
1687:Finite automata
1678:
1579:
1576:
1575:
1508:
1505:
1504:
1473:
1470:
1469:
1450:
1447:
1446:
1430:
1427:
1426:
1410:
1407:
1406:
1390:
1387:
1386:
1358:
1355:
1354:
1332:
1329:
1328:
1312:
1309:
1308:
1286:
1283:
1282:
1260:
1257:
1256:
1240:
1237:
1236:
1220:
1217:
1216:
1188:
1185:
1184:
1154:
1151:
1150:
1130:
1127:
1126:
1110:
1107:
1106:
1090:
1087:
1086:
1072:
1050:
1046:
1026:
1023:
1022:
991:
987:
967:
964:
963:
946:
942:
940:
937:
936:
920:
917:
916:
896:
893:
892:
872:
869:
868:
847:
843:
834:
830:
828:
825:
824:
803:
801:
800:
798:
795:
794:
762:
759:
758:
737:
733:
721:
717:
708:
704:
692:
688:
679:
675:
666:
662:
660:
657:
656:
634:
631:
630:
614:
611:
610:
594:
591:
590:
585:may not be the
570:
567:
566:
550:
547:
546:
530:
527:
526:
504:
501:
500:
467:
464:
463:
447:
444:
443:
419:
416:
415:
395:
392:
391:
367:
364:
363:
348:production rule
336:
307:
306:
292:Syntax analysis
267:Predicate logic
252:
251:
242:
241:
217:Automata theory
172:
171:
140:
129:
123:
120:
77:
75:
65:
53:
42:
35:
28:
23:
22:
15:
12:
11:
5:
1786:
1776:
1775:
1770:
1765:
1750:
1749:
1728:
1726:
1723:
1722:
1721:
1715:
1710:
1704:
1699:
1694:
1689:
1684:
1682:Formal grammar
1677:
1674:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1583:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1492:
1489:
1486:
1483:
1480:
1477:
1457:
1454:
1434:
1414:
1394:
1374:
1371:
1368:
1365:
1362:
1342:
1339:
1336:
1316:
1296:
1293:
1290:
1270:
1267:
1264:
1244:
1224:
1213:
1212:
1201:
1198:
1195:
1192:
1181:
1170:
1167:
1164:
1161:
1158:
1134:
1114:
1094:
1071:
1068:
1067:
1066:
1053:
1049:
1045:
1042:
1039:
1036:
1033:
1030:
994:
990:
986:
983:
980:
977:
974:
971:
949:
945:
924:
900:
876:
850:
846:
842:
837:
833:
806:
778:
775:
772:
769:
766:
755:
754:
740:
736:
732:
729:
724:
720:
716:
711:
707:
703:
700:
695:
691:
687:
682:
678:
674:
669:
665:
638:
618:
598:
574:
554:
534:
514:
511:
508:
477:
474:
471:
451:
423:
399:
384:formal grammar
371:
338:
337:
335:
334:
327:
320:
312:
309:
308:
305:
304:
299:
294:
289:
284:
279:
274:
269:
264:
259:
257:Formal methods
253:
249:
248:
247:
244:
243:
240:
239:
237:Atomic formula
234:
229:
224:
219:
214:
209:
207:Formation rule
204:
202:Formal grammar
199:
194:
189:
184:
179:
173:
169:
168:
167:
164:
163:
157:
156:
142:
141:
56:
54:
47:
26:
9:
6:
4:
3:
2:
1785:
1774:
1771:
1769:
1766:
1764:
1761:
1760:
1758:
1746:
1742:
1739:
1733:
1729:
1719:
1716:
1714:
1711:
1708:
1705:
1703:
1700:
1698:
1695:
1693:
1690:
1688:
1685:
1683:
1680:
1679:
1673:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1587:
1584:
1561:
1558:
1555:
1552:
1549:
1546:
1540:
1537:
1534:
1531:
1528:
1522:
1519:
1516:
1510:
1490:
1487:
1484:
1481:
1478:
1475:
1455:
1452:
1432:
1412:
1392:
1372:
1369:
1366:
1363:
1360:
1340:
1337:
1334:
1314:
1294:
1291:
1288:
1268:
1265:
1262:
1242:
1222:
1199:
1196:
1190:
1182:
1168:
1165:
1162:
1156:
1148:
1147:
1146:
1132:
1112:
1092:
1083:
1081:
1077:
1051:
1040:
1037:
1028:
1021:
1020:
1019:
1017:
1013:
1008:
992:
981:
972:
947:
943:
922:
914:
898:
890:
874:
866:
865:concatenation
848:
844:
840:
835:
831:
822:
804:
792:
773:
770:
767:
764:
738:
734:
730:
722:
709:
705:
698:
693:
689:
685:
680:
676:
672:
667:
663:
655:
654:
653:
652:
636:
616:
596:
588:
572:
552:
532:
512:
506:
498:
493:
491:
475:
472:
469:
449:
441:
437:
413:
397:
389:
385:
369:
361:
357:
353:
349:
345:
333:
328:
326:
321:
319:
314:
313:
311:
310:
303:
300:
298:
295:
293:
290:
288:
285:
283:
280:
278:
275:
273:
270:
268:
265:
263:
260:
258:
255:
254:
246:
245:
238:
235:
233:
230:
228:
225:
223:
220:
218:
215:
213:
210:
208:
205:
203:
200:
198:
195:
193:
190:
188:
185:
183:
180:
178:
177:Formal system
175:
174:
166:
165:
162:
159:
158:
154:
153:
148:
147:
138:
135:
127:
124:November 2012
116:
113:
109:
106:
102:
99:
95:
92:
88:
85: –
84:
80:
79:Find sources:
73:
69:
63:
62:
57:This article
55:
51:
46:
45:
40:
33:
19:
1732:
1702:Rewrite rule
1214:
1084:
1076:start symbol
1075:
1073:
1009:
790:
756:
587:empty string
494:
490:start symbol
489:
488:that is the
356:rewrite rule
347:
343:
341:
250:Applications
226:
170:Key concepts
151:
130:
121:
111:
104:
97:
90:
78:
66:Please help
61:verification
58:
821:Kleene star
360:recursively
1757:Categories
1725:References
863:indicates
823:operator,
791:vocabulary
344:production
227:Production
94:newspapers
39:Production
1657:…
1544:⇒
1526:⇒
1514:⇒
1194:→
1160:→
1080:ambiguous
1052:∗
1044:Σ
1041:∪
1032:→
993:∗
976:∖
948:∗
899:∖
889:set union
875:∪
849:∗
836:∗
805:∗
777:Σ
774:∪
739:∗
731:×
723:∗
719:Σ
715:∖
710:∗
694:∗
686:×
681:∗
668:∗
637:λ
617:ϵ
510:→
473:∈
422:Σ
1741:Archived
1697:L-system
1676:See also
911:denotes
887:denotes
525:, where
440:disjoint
438:that is
182:Alphabet
152:a series
149:Part of
1763:Grammar
819:is the
789:is the
108:scholar
891:, and
757:where
495:In an
187:Syntax
110:
103:
96:
89:
81:
1445:with
1327:with
1255:with
629:, or
589:. If
442:from
354:is a
115:JSTOR
101:books
1405:and
1105:and
545:and
87:news
1183:2.
1149:1.
962:by
434:of
410:of
350:in
346:or
70:by
1759::
1672:.
1082:.
867:,
793:,
768::=
492:.
342:A
155:on
1660:}
1654:,
1651:b
1648:b
1645:b
1642:a
1639:b
1636:a
1633:a
1630:a
1627:,
1624:b
1621:b
1618:a
1615:b
1612:a
1609:a
1606:,
1603:b
1600:a
1597:b
1594:a
1591:,
1588:a
1585:b
1582:{
1562:b
1559:b
1556:a
1553:b
1550:a
1547:a
1541:b
1538:b
1535:S
1532:a
1529:a
1523:b
1520:S
1517:a
1511:S
1491:b
1488:b
1485:a
1482:b
1479:a
1476:a
1456:a
1453:b
1433:S
1413:b
1393:a
1373:b
1370:b
1367:S
1364:a
1361:a
1341:b
1338:S
1335:a
1315:S
1295:b
1292:S
1289:a
1269:b
1266:S
1263:a
1243:S
1223:S
1200:a
1197:b
1191:S
1169:b
1166:S
1163:a
1157:S
1133:S
1113:b
1093:a
1048:)
1038:N
1035:(
1029:N
989:)
985:}
982:S
979:{
973:V
970:(
944:V
923:v
845:V
841:N
832:V
771:N
765:V
753:,
735:V
728:)
706:V
702:(
699:=
690:V
677:V
673:N
664:V
597:v
573:u
553:v
533:u
513:v
507:u
476:N
470:S
450:N
398:N
370:P
331:e
324:t
317:v
137:)
131:(
126:)
122:(
112:·
105:·
98:·
91:·
64:.
41:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
