3474:
3133:
28:
7358:
3469:{\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}{\underset {1}{\Rightarrow }}aB{\boldsymbol {aBSc}}c\\&{\underset {2}{\Rightarrow }}aBaB{\boldsymbol {abc}}cc\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}Babccc{\underset {3}{\Rightarrow }}aaB{\boldsymbol {aB}}bccc{\underset {3}{\Rightarrow }}aa{\boldsymbol {aB}}Bbccc\\&{\underset {4}{\Rightarrow }}aaaB{\boldsymbol {bb}}ccc{\underset {4}{\Rightarrow }}aaa{\boldsymbol {bb}}bccc\end{aligned}}}
3127:
4118:, the left hand side is again only a single nonterminal symbol, but now the right-hand side is also restricted. The right side may be the empty string, or a single terminal symbol, or a single terminal symbol followed by a nonterminal symbol, but nothing else. (Sometimes a broader definition is used: one can allow longer strings of terminals or single nonterminals without anything else, making languages
2963:
368:
The language generated by the grammar is defined to be the set of all strings without any nonterminal symbols that can be generated from the string consisting of a single start symbol by (possibly repeated) application of its rules in whatever way possible. If there are essentially different ways of
4705:
formal grammar, and that the goal is to transform this generative grammar into a working parser. Strictly speaking, a generative grammar does not in any way correspond to the algorithm used to parse a language, and various algorithms have different restrictions on the form of production rules that
4623:
Many extensions and variations on
Chomsky's original hierarchy of formal grammars have been developed, both by linguists and by computer scientists, usually either in order to increase their expressive power or in order to make them easier to analyze or parse. Some forms of grammars developed
3122:{\displaystyle {\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}\\&{\underset {2}{\Rightarrow }}aB{\boldsymbol {abc}}c\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}bcc\\&{\underset {4}{\Rightarrow }}aa{\boldsymbol {bb}}cc\end{aligned}}}
1929:
1496:. That is, each production rule maps from one string of symbols to another, where the first string (the "head") contains an arbitrary number of symbols provided at least one of them is a nonterminal. In the case that the second string (the "body") consists solely of the
4709:
An alternative approach is to formalize the language in terms of an analytic grammar in the first place, which more directly corresponds to the structure and semantics of a parser for the language. Examples of analytic grammar formalisms include the following:
2144:
3611:
is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. This restriction is non-trivial; not all languages can be generated by context-free grammars. Those that can are called
1440:
2957:
715:
288:
of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, a grammar is usually thought of as a language generator. However, it can also sometimes be used as the basis for a
293:"—a function in computing that determines whether a given string belongs to the language or is grammatically incorrect. To describe such recognizers, formal language theory uses separate formalisms, known as
1775:
567:
3701:
2767:
1965:
4247:
4182:
3764:
3138:
2968:
3512:
2000:
1729:
305:
of symbols and analyzing each one against the grammar of the language. Most languages have the meanings of their utterances structured according to their syntax—a practice known as
2499:
5082:
4645:
allow rewrite rules to be augmented with semantic attributes and operations, useful both for increasing grammar expressiveness and for constructing practical language translation tools.
4404:
3907:
343:). A rule can be applied to each string that contains its left-hand side and produces a string in which an occurrence of that left-hand side has been replaced with its right-hand side.
5262:
4575:
4362:
5144:
2451:
2233:
2045:
1768:
3865:
31:
An example of a formal grammar with parsed sentence. Formal grammars consist of a set of non-terminal symbols, terminal symbols, production rules, and a designated start symbol.
3585:, these two restricted types of grammars are most often used because parsers for them can be efficiently implemented. For example, all regular languages can be recognized by a
2578:
2348:
2307:
1702:
3963:
2680:
2646:
2612:
2070:
909:
430:
5737:
4548:
4518:
4488:
4458:
3994:
1632:
1192:
1161:
875:
461:
4615:, some forms of regular expression used in practice do not strictly generate the regular languages and do not show linear recognitional performance due to those deviations.
1248:
1220:
844:
4106:
is a subset of context-free languages that can be recognized in linear time. There exist various algorithms that target either this set of languages or some subset of it.
2171:
1542:
6412:
4080:
4033:
1518:
3553:. The difference between these types is that they have increasingly strict production rules and can therefore express fewer formal languages. Two important types are
1320:
1573:
4314:
3831:
2794:
1490:
742:
4609:
2910:
1466:
1041:
309:. As a result, the first step to describing the meaning of an utterance in language is to break it down part by part and look at its analyzed form (known as its
4424:
4287:
4267:
4100:
3927:
3804:
3784:
2878:
2858:
2838:
2818:
2539:
2519:
2409:
2372:
2253:
2202:
2065:
1121:
1101:
1081:
1061:
1015:
995:
975:
955:
932:
802:
782:
762:
6495:
5636:
5582:
1356:
5255:
221:
5027:
2919:
575:
3704:
6809:
914:
This grammar is not context-free due to rule 3 and it is ambiguous due to the multiple ways in which rule 2 can be used to generate sequences of
5469:
5248:
4882:
6967:
4976:
4948:
5755:
4681:
as the leftmost symbol. An example of recursive grammar is a clause within a sentence separated by two commas. All types of grammars in the
1924:{\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}
6822:
6145:
5394:
314:
501:
5484:
5141:
4103:
6407:
6827:
6817:
6554:
5760:
5409:
6305:
5751:
3622:
2688:
6963:
4994:
4857:
297:. One of the interesting results of automata theory is that it is not possible to design a recognizer for certain formal languages.
361:; each left-hand side must contain at least one nonterminal symbol. It also distinguishes a special nonterminal symbol, called the
7060:
6804:
5629:
5577:
5562:
1938:
351:
6365:
6058:
5799:
7402:
5438:
4738:
7321:
7023:
6786:
6781:
6606:
6027:
5711:
4187:
4790:
4128:
3710:
7316:
7099:
7016:
6729:
6660:
6537:
5779:
2354:
symbols, which must be rewritten in rewrite rules, and are only interested in rewritings from the designated start symbol
331:
255:
118:
6387:
7241:
7067:
6753:
5986:
5455:
5380:
4662:
1972:
266:
88:
6392:
7392:
6724:
6463:
5721:
5622:
5552:
5151:, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.
239:
173:
168:
73:
7119:
7114:
3484:
214:
7048:
6638:
6032:
6000:
5691:
5448:
5225:
4734:
1978:
1707:
5765:
4046:. That is, for every context-free language, a machine can be built that takes a string as input and determines in
2456:
7382:
7338:
7287:
7184:
6682:
6643:
6120:
5373:
5112:
4714:
207:
193:
178:
42:
7179:
5794:
4367:
3870:
27:
7109:
6648:
6500:
6483:
6206:
5686:
5525:
5520:
1639:
274:
5606:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
4717:(TDPL): a highly minimalist analytic grammar formalism developed in the early 1970s to study the behavior of
1126:
That same language can alternatively be generated by a context-free, nonambiguous grammar; for instance, the
7011:
6988:
6949:
6835:
6776:
6422:
6342:
6186:
6130:
5743:
5024:
4554:
4319:
306:
270:
254:
or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of
7301:
7028:
7006:
6973:
6866:
6712:
6697:
6670:
6621:
6505:
6440:
6265:
6231:
6226:
6100:
5931:
5908:
5536:
5474:
5399:
4628:
2414:
2207:
335:, rewriting rules for transforming strings. Each rule specifies a replacement of a particular string (its
153:
2139:{\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}
2011:
1734:
7231:
7084:
6876:
6594:
6330:
6236:
6095:
6080:
5961:
5936:
5479:
5427:
5240:
4815:
4666:
4631:
increase the expressiveness of conventional generative grammars by allowing rewrite rules to operate on
3836:
3589:, and for useful subsets of context-free grammars there are well-known algorithms to generate efficient
3567:
350:, which is wholly defined by these rules, a grammar further distinguishes between two kinds of symbols:
163:
7357:
4775:
2548:
2315:
2262:
1657:
1500:—i.e., that it contains no symbols at all—it may be denoted with a special notation (often
3936:
2653:
2619:
2585:
882:
403:
7204:
7166:
7043:
6847:
6687:
6611:
6589:
6417:
6375:
6274:
6241:
6105:
5893:
5804:
5572:
5547:
5404:
5365:
4785:
4760:
4742:
4731:, which derives syntactic structure by examining the positional relationships between pairs of words.
4524:
4494:
4464:
4434:
3970:
3607:
3586:
3578:
3555:
2384:
1593:
1259:
1168:
1137:
851:
805:
437:
4611:
time by a finite-state machine. Although in practice, regular grammars are commonly expressed using
2350:, rewriting strings in exactly the same way; the only difference is in that we distinguish specific
1227:
1199:
823:
301:
is the process of recognizing an utterance (a string in natural languages) by breaking it down to a
7333:
7224:
7209:
7189:
7146:
7033:
6983:
6909:
6854:
6791:
6584:
6579:
6527:
6295:
6284:
5956:
5856:
5784:
5775:
5771:
5706:
5701:
4964:
4864:
4825:
262:
188:
103:
804:
in particular represents the number of times production rule 1 has been applied). This grammar is
261:
Formal language theory, the discipline that studies formal grammars and languages, is a branch of
7362:
7131:
7094:
7079:
7072:
7055:
6841:
6707:
6633:
6616:
6569:
6382:
6291:
6125:
6110:
6070:
6022:
6007:
5995:
5951:
5926:
5696:
5645:
5557:
5499:
5443:
4899:
4780:
4655:
4612:
3540:
2149:
1493:
1287:
318:
278:
113:
83:
6859:
6315:
1527:
7297:
7104:
6914:
6904:
6796:
6677:
6512:
6488:
6269:
6253:
6158:
6135:
6012:
5981:
5946:
5841:
5676:
5292:
4972:
4944:
4922:
4853:
4847:
4800:
4770:
4694:
4682:
4642:
4049:
4002:
3550:
3536:
1503:
370:
302:
285:
123:
3549:
first formalized generative grammars in 1956, he classified them into types now known as the
1305:
7387:
7311:
7306:
7199:
7156:
6978:
6939:
6934:
6919:
6745:
6702:
6599:
6397:
6347:
5921:
5883:
5541:
5494:
5461:
5307:
5060:
4936:
4891:
4765:
4718:
3573:
2310:
1635:
1552:
347:
52:
5152:
4292:
3809:
2772:
1475:
937:
However, the language it generates is simply the set of all nonempty strings consisting of
720:
7397:
7292:
7282:
7236:
7219:
7174:
7136:
7038:
6958:
6765:
6692:
6665:
6653:
6559:
6473:
6447:
6402:
6370:
6171:
5973:
5916:
5866:
5831:
5789:
5504:
5419:
5386:
5302:
5275:
5271:
5148:
5031:
4998:
4585:
4119:
4115:
3561:
2886:
1324:
294:
243:
183:
158:
108:
4991:
1449:
1020:
5188:, Doctoral thesis, Princeton University, Dept. of Electrical Engineering, February 1970.
3703:
defined above is not a context-free language, and this can be strictly proven using the
7277:
7256:
7214:
7194:
7089:
6944:
6542:
6532:
6517:
6451:
6325:
6201:
6090:
6085:
6063:
5664:
5515:
4670:
4409:
4272:
4252:
4085:
4039:
3912:
3789:
3769:
3582:
2863:
2843:
2823:
2803:
2524:
2504:
2394:
2357:
2238:
2187:
2050:
1106:
1086:
1066:
1046:
1000:
980:
960:
940:
917:
787:
767:
747:
148:
128:
98:
78:
5064:
1435:{\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}
7376:
7251:
6929:
6436:
6221:
6211:
6181:
6166:
5836:
5600:
5201:," Technical Report CMU-CS-91-196, Carnegie Mellon University Computer Science, 1991.
4820:
4638:
4043:
1329:
1292:
68:
4903:
7151:
6998:
6899:
6891:
6771:
6719:
6628:
6564:
6547:
6478:
6337:
6196:
5898:
5681:
5048:
4724:
3546:
1497:
1270:
470:, and can choose a rule to apply to it. If we choose rule 1, we obtain the string
2952:{\displaystyle {\boldsymbol {S}}{\underset {2}{\Rightarrow }}{\boldsymbol {abc}}}
498:, and are done. We can write this series of choices more briefly, using symbols:
7261:
7141:
6320:
6310:
6257:
5941:
5861:
5846:
5726:
5671:
5567:
5489:
5414:
5210:
Sleator, Daniel D. & Temperly, Davy, "Parsing
English with a Link Grammar,"
5184:
4728:
1469:
710:{\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}
17:
6191:
6046:
6017:
5823:
4697:, most of these algorithms assume that the language to be parsed is initially
4632:
4289:, where the numbers may be different) is, as it can be defined by the grammar
2146:. A sentential form that contains no nonterminal symbols (i.e. is a member of
310:
290:
5165:
4895:
3565:(Type 3). The languages that can be described with such a grammar are called
7343:
7246:
6299:
6216:
6176:
6140:
6076:
5888:
5878:
5851:
3594:
3590:
1650:
The operation of a grammar can be defined in terms of relations on strings:
251:
4737:(PEGs): a more recent generalization of TDPL designed around the practical
3581:(Type 0), which can in fact express any language that can be accepted by a
4880:
Chomsky, Noam (Sep 1956). "Three models for the description of language".
7328:
7126:
6574:
6279:
5873:
4805:
4746:
4661:
A recursive grammar is a grammar that contains production rules that are
6924:
5716:
5198:
4795:
2820:'s. Thus, the language is the set of strings that consist of 1 or more
298:
5128:
Knuth, Donald E., "Semantics of
Context-Free Languages (correction),"
4677:
that can be put through the production rules to produce a string with
2047:
that can be derived in a finite number of steps from the start symbol
1269:
In the classic formalization of generative grammars first proposed by
808:(only single nonterminals appear as left-hand sides) and unambiguous.
5614:
5229:, Master’s thesis, Massachusetts Institute of Technology, Sept. 2002.
4810:
247:
5226:
Packrat
Parsing: a Practical Linear-Time Algorithm with Backtracking
5051:(July 1965). "On the translation of languages from left to right".
562:{\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}
6468:
5814:
5659:
5530:
4582:
All languages generated by a regular grammar can be recognized in
3597:
to recognize the corresponding languages those grammars generate.
1588:
26:
4971:. Reading, Mass.: Addison-Wesley Publishing Company. p. 13.
5618:
5244:
5102:, North Holland Publishing Company, Amsterdam, p. 95-109, 1971.
4941:
Algebraic and automata theoretic properties of formal languages
4849:
Formal
Languages and Computation: Models and Their Applications
3696:{\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}
3526:", and the generated part is each time indicated in bold type.)
2762:{\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}
1063:. This means we can generate arbitrary nonempty sequences of
369:
generating the same single string, the grammar is said to be
5599:
Each category of languages, except those marked by a , is a
4082:
time whether the string is a member of the language, where
1960:{\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}
3806:'s) is context-free, as it can be defined by the grammar
2383:
For these examples, formal languages are specified using
4242:{\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}
1731:(pronounced as "G derives in one step") on strings in
4426:
the start symbol, and the following production rules:
3929:
the start symbol, and the following production rules:
1646:
Some mathematical constructs regarding formal grammars
4588:
4557:
4527:
4497:
4467:
4437:
4412:
4370:
4322:
4295:
4275:
4255:
4190:
4177:{\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}
4131:
4088:
4052:
4005:
3973:
3939:
3915:
3873:
3839:
3812:
3792:
3772:
3759:{\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}
3713:
3625:
3487:
3136:
2966:
2922:
2889:
2866:
2846:
2826:
2806:
2775:
2691:
2656:
2622:
2588:
2551:
2527:
2507:
2459:
2417:
2397:
2360:
2318:
2265:
2241:
2210:
2190:
2152:
2073:
2053:
2014:
1981:
1941:
1778:
1737:
1710:
1660:
1596:
1555:
1530:
1506:
1478:
1452:
1359:
1308:
1230:
1202:
1171:
1140:
1109:
1089:
1069:
1049:
1023:
1003:
983:
963:
943:
920:
885:
854:
826:
790:
770:
750:
723:
578:
504:
440:
406:
5212:
376:
In the following examples, the terminal symbols are
7270:
7165:
6997:
6890:
6742:
6435:
6358:
6252:
6156:
6045:
5972:
5907:
5822:
5813:
5735:
5652:
4693:Though there is a tremendous body of literature on
4122:while still defining the same class of languages.)
4603:
4569:
4542:
4512:
4482:
4452:
4418:
4398:
4356:
4308:
4281:
4261:
4241:
4176:
4094:
4074:
4027:
3988:
3957:
3921:
3901:
3859:
3825:
3798:
3778:
3758:
3695:
3506:
3468:
3121:
2951:
2904:
2872:
2852:
2832:
2812:
2788:
2761:
2674:
2640:
2606:
2572:
2533:
2513:
2493:
2445:
2403:
2366:
2342:
2301:
2247:
2227:
2196:
2165:
2138:
2059:
2039:
1994:
1959:
1923:
1762:
1723:
1696:
1626:
1567:
1536:
1512:
1484:
1460:
1434:
1314:
1242:
1214:
1186:
1155:
1115:
1095:
1075:
1055:
1035:
1009:
989:
969:
949:
926:
903:
869:
838:
796:
776:
756:
736:
709:
561:
455:
424:
3577:, respectively. Although much less powerful than
572:The language of the grammar is the infinite set
396:Suppose we have the following production rules:
4184:defined above is not regular, but the language
3507:{\displaystyle P{\underset {i}{\Rightarrow }}Q}
1043:, then rule 1 twice and rule 3 once to produce
5098:Koster , Cornelis H. A., "Affix Grammars," in
2883:Some examples of the derivation of strings in
2235:, is defined as the set of sentences built by
5630:
5256:
4875:
4873:
3999:A context-free language can be recognized in
1995:{\displaystyle {\underset {G}{\Rightarrow }}}
1724:{\displaystyle {\underset {G}{\Rightarrow }}}
474:. If we then choose rule 1 again, we replace
215:
8:
5012:Parsing Techniques – A Practical Guide
2541:consists of the following production rules:
2494:{\displaystyle \Sigma =\left\{a,b,c\right\}}
2067:; that is, a sentential form is a member of
704:
626:
620:
579:
5578:Counter-free (with aperiodic finite monoid)
5142:Notes on Formal Language Theory and Parsing
5038:, Vol. 13 No. 2, pp. 94-102, February 1970.
5025:An Efficient Context-Free Parsing Algorithm
6456:
6051:
5819:
5637:
5623:
5615:
5288:
5263:
5249:
5241:
5214:, 1993. (Revised version of above report.)
5197:Sleator, Daniel D. & Temperly, Davy, "
4727:: a form of analytic grammar designed for
4399:{\displaystyle \Sigma =\left\{a,b\right\}}
3902:{\displaystyle \Sigma =\left\{a,b\right\}}
1799:
1795:
1634:. Such a formal grammar is often called a
222:
208:
37:
4587:
4556:
4526:
4496:
4466:
4436:
4411:
4369:
4321:
4300:
4294:
4274:
4254:
4210:
4200:
4189:
4151:
4141:
4130:
4087:
4063:
4051:
4016:
4004:
3972:
3938:
3914:
3872:
3838:
3817:
3811:
3791:
3771:
3733:
3723:
3712:
3670:
3660:
3650:
3624:
3491:
3486:
3442:
3423:
3406:
3384:
3354:
3338:
3318:
3299:
3273:
3260:
3236:
3214:
3190:
3174:
3160:
3150:
3141:
3137:
3135:
3101:
3085:
3061:
3048:
3027:
3011:
2990:
2980:
2971:
2967:
2965:
2938:
2928:
2923:
2921:
2888:
2865:
2845:
2825:
2805:
2780:
2774:
2736:
2726:
2716:
2690:
2655:
2621:
2587:
2550:
2526:
2506:
2458:
2416:
2396:
2359:
2317:
2264:
2240:
2211:
2209:
2189:
2157:
2151:
2113:
2101:
2072:
2052:
2031:
2013:
1982:
1980:
1942:
1940:
1843:
1782:
1777:
1754:
1736:
1711:
1709:
1659:
1595:
1554:
1529:
1505:
1477:
1453:
1451:
1426:
1401:
1376:
1358:
1307:
1229:
1201:
1170:
1139:
1108:
1088:
1068:
1048:
1022:
1002:
982:
962:
942:
919:
884:
853:
825:
789:
769:
749:
728:
722:
602:
586:
577:
503:
439:
405:
3705:pumping lemma for context-free languages
2374:to strings without nonterminal symbols.
5172:. p. 2 – via Newspapers.com.
5001:, Context-Free Grammars, David Matuszek
4838:
3446:
3443:
3410:
3407:
3358:
3355:
3322:
3319:
3277:
3274:
3243:
3240:
3237:
3200:
3197:
3194:
3191:
3170:
3167:
3164:
3161:
3142:
3105:
3102:
3065:
3062:
3034:
3031:
3028:
3000:
2997:
2994:
2991:
2972:
2945:
2942:
2939:
2924:
2212:
258:for such strings in a formal language.
51:
5470:Linear context-free rewriting language
4969:Introduction to Formal Language Theory
4883:IRE Transactions on Information Theory
4673:if there exists a non-terminal symbol
4570:{\displaystyle B\rightarrow \epsilon }
4357:{\displaystyle N=\left\{S,A,B\right\}}
1277:consists of the following components:
977:s. This is easy to see: to generate a
486:. If we now choose rule 2, we replace
329:A grammar mainly consists of a set of
246:are valid according to the language's
5395:Linear context-free rewriting systems
5010:Grune, Dick & Jacobs, Ceriel H.,
1587:A grammar is formally defined as the
1127:
1083:s and then replace each of them with
816:Suppose the rules are these instead:
7:
4104:Deterministic context-free languages
2446:{\displaystyle N=\left\{S,B\right\}}
2228:{\displaystyle {\boldsymbol {L}}(G)}
5199:Parsing English with a Link Grammar
5164:Borenstein, Seth (April 27, 2006).
5113:Semantics of Context-Free Languages
5089:, Vol. 10 No. 1, pp. 136-163, 1975.
5087:Journal of Computer Systems Science
2860:'s, followed by the same number of
2840:'s, followed by the same number of
2040:{\displaystyle (\Sigma \cup N)^{*}}
1763:{\displaystyle (\Sigma \cup N)^{*}}
5603:of the category directly above it.
5119:, Vol. 2 No. 2, pp. 127-145, 1968.
4619:Other forms of generative grammars
4371:
3874:
3860:{\displaystyle N=\left\{S\right\}}
2685:This grammar defines the language
2460:
2328:
2281:
2154:
2088:
2018:
1830:
1800:
1741:
1676:
1606:
1507:
1413:
1388:
1363:
1309:
250:. A grammar does not describe the
25:
2573:{\displaystyle S\rightarrow aBSc}
2343:{\displaystyle (N\cup \Sigma ,P)}
2302:{\displaystyle G=(N,\Sigma ,P,S)}
1697:{\displaystyle G=(N,\Sigma ,P,S)}
265:. Its applications are found in
89:Semantics (programming languages)
7356:
4863:. For more on this subject, see
4791:Extended Backus–Naur form (EBNF)
3958:{\displaystyle S\rightarrow aSb}
2675:{\displaystyle Bb\rightarrow bb}
2641:{\displaystyle Ba\rightarrow aB}
2607:{\displaystyle S\rightarrow abc}
904:{\displaystyle aSa\rightarrow b}
425:{\displaystyle S\rightarrow aSb}
313:in computer science, and as its
238:describes which strings from an
5132:, Vol. 5 No. 1, pp 95-96, 1971.
5014:, Ellis Horwood, England, 1990.
4943:. North-Holland. pp. 8–9.
4665:. For example, a grammar for a
4543:{\displaystyle B\rightarrow bB}
4513:{\displaystyle A\rightarrow bB}
4483:{\displaystyle A\rightarrow aA}
4453:{\displaystyle S\rightarrow aA}
3989:{\displaystyle S\rightarrow ab}
3786:followed by the same number of
3707:, but for example the language
1969:G derives in zero or more steps
1627:{\displaystyle (N,\Sigma ,P,S)}
1187:{\displaystyle S\rightarrow bS}
1156:{\displaystyle S\rightarrow aS}
1017:, use rule 2 twice to generate
870:{\displaystyle S\rightarrow SS}
456:{\displaystyle S\rightarrow ba}
5166:"Songbirds grasp grammar, too"
4598:
4592:
4561:
4531:
4501:
4471:
4441:
4069:
4056:
4022:
4009:
3977:
3943:
3635:
3629:
3493:
3425:
3386:
3340:
3301:
3262:
3216:
3176:
3152:
3087:
3050:
3013:
2982:
2930:
2899:
2893:
2701:
2695:
2663:
2629:
2592:
2555:
2337:
2319:
2296:
2272:
2222:
2216:
2116:
2098:
2085:
2028:
2015:
1984:
1945:
1918:
1900:
1894:
1882:
1876:
1870:
1852:
1840:
1827:
1796:
1784:
1751:
1738:
1713:
1691:
1667:
1621:
1597:
1544:) in order to avoid confusion.
1423:
1410:
1407:
1398:
1385:
1373:
1360:
1243:{\displaystyle S\rightarrow b}
1234:
1215:{\displaystyle S\rightarrow a}
1206:
1175:
1144:
895:
858:
839:{\displaystyle S\rightarrow a}
830:
538:
520:
508:
444:
410:
35:Structure of a formal language
1:
7317:History of mathematical logic
5065:10.1016/S0019-9958(65)90426-2
4102:is the length of the string.
1295:with the strings formed from
7242:Primitive recursive function
4706:are considered well-formed.
1973:reflexive transitive closure
267:theoretical computer science
5130:Mathematical Systems Theory
5117:Mathematical Systems Theory
4735:Parsing expression grammars
2166:{\displaystyle \Sigma ^{*}}
174:Programming language theory
169:Natural language processing
7419:
6306:Schröder–Bernstein theorem
6033:Monadic predicate calculus
5692:Foundations of mathematics
5485:Deterministic context-free
5410:Deterministic context-free
5185:The TMG Recognition Schema
4852:, CRC Press, p. 233,
4846:Meduna, Alexander (2014),
4653:
4042:) by an algorithm such as
3534:
1257:
384:, and the start symbol is
7352:
7339:Philosophy of mathematics
7288:Automated theorem proving
6459:
6413:Von Neumann–Bernays–Gödel
6054:
5596:
5558:Nondeterministic pushdown
5286:
5036:Communications of the ACM
4715:Top-down parsing language
2521:is the start symbol, and
1537:{\displaystyle \epsilon }
194:Automated theorem proving
179:Computational linguistics
4896:10.1109/TIT.1956.1056813
4654:Not to be confused with
4635:instead of just strings.
4075:{\displaystyle O(n^{3})}
4028:{\displaystyle O(n^{3})}
1640:phrase structure grammar
1513:{\displaystyle \Lambda }
1273:in the 1950s, a grammar
6989:Self-verifying theories
6810:Tarski's axiomatization
5761:Tarski's undefinability
5756:incompleteness theorems
5100:ALGOL 68 Implementation
5053:Information and Control
4629:Tree-adjoining grammars
4269:followed by at least 1
3522:by means of production
1549:A distinguished symbol
1347:, each rule of the form
1315:{\displaystyle \Sigma }
307:compositional semantics
271:theoretical linguistics
7403:Automata (computation)
7363:Mathematics portal
6974:Proof of impossibility
6622:propositional variable
5932:Propositional calculus
5563:Deterministic pushdown
5439:Recursively enumerable
4917:Chomsky, Noam (1957).
4776:Backus–Naur form (BNF)
4605:
4571:
4544:
4514:
4484:
4454:
4420:
4400:
4358:
4310:
4283:
4263:
4243:
4178:
4096:
4076:
4029:
3990:
3959:
3923:
3903:
3861:
3827:
3800:
3780:
3760:
3697:
3614:context-free languages
3568:context-free languages
3508:
3470:
3123:
2953:
2906:
2874:
2854:
2834:
2814:
2790:
2763:
2676:
2642:
2608:
2574:
2535:
2515:
2495:
2447:
2405:
2368:
2344:
2303:
2249:
2229:
2198:
2167:
2140:
2061:
2041:
1996:
1961:
1925:
1764:
1725:
1704:, the binary relation
1698:
1628:
1569:
1568:{\displaystyle S\in N}
1538:
1514:
1486:
1462:
1436:
1316:
1265:The syntax of grammars
1244:
1216:
1188:
1157:
1117:
1097:
1077:
1057:
1037:
1011:
991:
971:
951:
928:
905:
871:
840:
798:
778:
758:
738:
711:
563:
494:and obtain the string
482:and obtain the string
457:
426:
284:A formal grammar is a
252:meaning of the strings
154:Propositional calculus
32:
7232:Kolmogorov complexity
7185:Computably enumerable
7085:Model complete theory
6877:Principia Mathematica
5937:Propositional formula
5766:Banach–Tarski paradox
5083:Tree Adjunct Grammars
4816:Post canonical system
4667:context-free language
4606:
4572:
4545:
4515:
4485:
4455:
4421:
4401:
4359:
4311:
4309:{\displaystyle G_{3}}
4284:
4264:
4244:
4179:
4097:
4077:
4030:
3991:
3960:
3924:
3904:
3862:
3828:
3826:{\displaystyle G_{2}}
3801:
3781:
3761:
3698:
3601:Context-free grammars
3579:unrestricted grammars
3556:context-free grammars
3531:The Chomsky hierarchy
3509:
3471:
3124:
2954:
2907:
2875:
2855:
2835:
2815:
2791:
2789:{\displaystyle a^{n}}
2764:
2677:
2643:
2609:
2575:
2536:
2516:
2496:
2448:
2406:
2391:Consider the grammar
2369:
2345:
2304:
2250:
2230:
2199:
2168:
2141:
2062:
2042:
1997:
1962:
1926:
1765:
1726:
1699:
1629:
1570:
1539:
1515:
1487:
1485:{\displaystyle \cup }
1463:
1437:
1317:
1245:
1217:
1189:
1158:
1118:
1098:
1078:
1058:
1038:
1012:
992:
972:
952:
929:
906:
872:
841:
799:
779:
759:
739:
737:{\displaystyle a^{k}}
712:
564:
458:
427:
164:Mathematical notation
30:
7180:Church–Turing thesis
7167:Computability theory
6376:continuum hypothesis
5894:Square of opposition
5752:Gödel's completeness
5548:Tree stack automaton
4965:Harrison, Michael A.
4919:Syntactic Structures
4786:Concrete syntax tree
4761:Abstract syntax tree
4743:programming language
4604:{\displaystyle O(n)}
4586:
4555:
4525:
4495:
4465:
4435:
4410:
4368:
4320:
4293:
4273:
4253:
4188:
4129:
4086:
4050:
4003:
3971:
3937:
3913:
3871:
3837:
3810:
3790:
3770:
3711:
3623:
3608:context-free grammar
3587:finite-state machine
3485:
3134:
2964:
2920:
2905:{\displaystyle L(G)}
2887:
2864:
2844:
2824:
2804:
2796:denotes a string of
2773:
2689:
2654:
2620:
2586:
2549:
2525:
2505:
2457:
2415:
2395:
2385:set-builder notation
2358:
2316:
2263:
2239:
2208:
2188:
2150:
2071:
2051:
2012:
1979:
1971:) is defined as the
1939:
1776:
1735:
1708:
1658:
1594:
1553:
1528:
1504:
1476:
1450:
1357:
1306:
1260:Unrestricted grammar
1228:
1200:
1169:
1138:
1107:
1087:
1067:
1047:
1021:
1001:
981:
961:
941:
918:
883:
852:
824:
788:
768:
748:
721:
576:
502:
438:
404:
339:) with another (its
325:Introductory example
7334:Mathematical object
7225:P versus NP problem
7190:Computable function
6984:Reverse mathematics
6910:Logical consequence
6787:primitive recursive
6782:elementary function
6555:Free/bound variable
6408:Tarski–Grothendieck
5927:Logical connectives
5857:Logical equivalence
5707:Logical consequence
5456:range concatenation
5381:range concatenation
5182:Birman, Alexander,
5111:Knuth, Donald E., "
5077:Joshi, Aravind K.,
4865:undecidable problem
4826:Well-formed formula
4613:regular expressions
4044:Earley's recogniser
2309:is effectively the
1642:in the literature.
1461:{\displaystyle {*}}
1288:nonterminal symbols
1130:grammar with rules
1036:{\displaystyle SSS}
466:then we start with
281:, and other areas.
263:applied mathematics
189:Formal verification
104:Well-formed formula
7393:Mathematical logic
7132:Transfer principle
7095:Semantics of logic
7080:Categorical theory
7056:Non-standard model
6570:Logical connective
5697:Information theory
5646:Mathematical logic
5147:2017-08-28 at the
5030:2020-05-19 at the
4997:2019-11-13 at the
4781:Categorial grammar
4695:parsing algorithms
4685:can be recursive.
4656:Recursive language
4650:Recursive grammars
4643:attribute grammars
4601:
4567:
4540:
4510:
4480:
4450:
4416:
4396:
4354:
4306:
4279:
4259:
4239:
4174:
4092:
4072:
4025:
3986:
3955:
3919:
3899:
3857:
3823:
3796:
3776:
3756:
3693:
3541:Generative grammar
3504:
3499:
3466:
3464:
3431:
3392:
3346:
3307:
3268:
3222:
3182:
3158:
3119:
3117:
3093:
3056:
3019:
2988:
2949:
2936:
2902:
2870:
2850:
2830:
2810:
2786:
2759:
2672:
2638:
2604:
2570:
2531:
2511:
2491:
2443:
2401:
2364:
2340:
2299:
2245:
2225:
2194:
2163:
2136:
2122:
2057:
2037:
1992:
1990:
1957:
1951:
1921:
1790:
1760:
1721:
1719:
1694:
1624:
1579:, also called the
1565:
1534:
1510:
1482:
1458:
1432:
1312:
1240:
1212:
1184:
1153:
1113:
1093:
1073:
1053:
1033:
1007:
987:
967:
947:
924:
901:
867:
836:
794:
774:
754:
734:
707:
559:
453:
422:
319:generative grammar
279:mathematical logic
114:Regular expression
33:
7370:
7369:
7302:Abstract category
7105:Theories of truth
6915:Rule of inference
6905:Natural deduction
6886:
6885:
6431:
6430:
6136:Cartesian product
6041:
6040:
5947:Many-valued logic
5922:Boolean functions
5805:Russell's paradox
5780:diagonal argument
5677:First-order logic
5612:
5611:
5591:
5590:
5553:Embedded pushdown
5449:Context-sensitive
5374:Context-sensitive
5308:Abstract machines
5293:Chomsky hierarchy
4978:978-0-201-02955-0
4950:978-0-7204-2506-2
4937:Ginsburg, Seymour
4801:Grammar framework
4771:Ambiguous grammar
4689:Analytic grammars
4683:Chomsky hierarchy
4419:{\displaystyle S}
4282:{\displaystyle b}
4262:{\displaystyle a}
4095:{\displaystyle n}
3922:{\displaystyle S}
3799:{\displaystyle b}
3779:{\displaystyle a}
3574:regular languages
3551:Chomsky hierarchy
3537:Chomsky hierarchy
3518:generates string
3492:
3424:
3385:
3339:
3300:
3261:
3215:
3175:
3151:
3086:
3049:
3012:
2981:
2929:
2873:{\displaystyle c}
2853:{\displaystyle b}
2833:{\displaystyle a}
2813:{\displaystyle a}
2534:{\displaystyle P}
2514:{\displaystyle S}
2404:{\displaystyle G}
2367:{\displaystyle S}
2248:{\displaystyle G}
2197:{\displaystyle G}
2126:
2115:
2060:{\displaystyle S}
1983:
1955:
1944:
1783:
1712:
1254:Formal definition
1116:{\displaystyle b}
1096:{\displaystyle a}
1076:{\displaystyle S}
1056:{\displaystyle b}
1010:{\displaystyle S}
990:{\displaystyle b}
970:{\displaystyle b}
950:{\displaystyle a}
927:{\displaystyle S}
797:{\displaystyle n}
777:{\displaystyle k}
757:{\displaystyle a}
232:
231:
124:Ground expression
84:Semantics (logic)
16:(Redirected from
7410:
7383:Formal languages
7361:
7360:
7312:History of logic
7307:Category of sets
7200:Decision problem
6979:Ordinal analysis
6920:Sequent calculus
6818:Boolean algebras
6758:
6757:
6732:
6703:logical/constant
6457:
6443:
6366:Zermelo–Fraenkel
6117:Set operations:
6052:
5989:
5820:
5800:Löwenheim–Skolem
5687:Formal semantics
5639:
5632:
5625:
5616:
5607:
5604:
5568:Visibly pushdown
5542:Thread automaton
5490:Visibly pushdown
5458:
5415:Visibly pushdown
5383:
5370:(no common name)
5289:
5276:formal languages
5265:
5258:
5251:
5242:
5230:
5221:
5215:
5208:
5202:
5195:
5189:
5180:
5174:
5173:
5170:Northwest Herald
5161:
5155:
5139:
5133:
5126:
5120:
5109:
5103:
5096:
5090:
5075:
5069:
5068:
5045:
5039:
5021:
5015:
5008:
5002:
4992:Sentential Forms
4989:
4983:
4982:
4961:
4955:
4954:
4933:
4927:
4926:
4914:
4908:
4907:
4877:
4868:
4862:
4843:
4766:Adaptive grammar
4719:top-down parsers
4610:
4608:
4607:
4602:
4576:
4574:
4573:
4568:
4549:
4547:
4546:
4541:
4519:
4517:
4516:
4511:
4489:
4487:
4486:
4481:
4459:
4457:
4456:
4451:
4425:
4423:
4422:
4417:
4405:
4403:
4402:
4397:
4395:
4391:
4363:
4361:
4360:
4355:
4353:
4349:
4315:
4313:
4312:
4307:
4305:
4304:
4288:
4286:
4285:
4280:
4268:
4266:
4265:
4260:
4248:
4246:
4245:
4240:
4238:
4234:
4215:
4214:
4205:
4204:
4183:
4181:
4180:
4175:
4173:
4169:
4156:
4155:
4146:
4145:
4120:easier to denote
4116:regular grammars
4110:Regular grammars
4101:
4099:
4098:
4093:
4081:
4079:
4078:
4073:
4068:
4067:
4034:
4032:
4031:
4026:
4021:
4020:
3995:
3993:
3992:
3987:
3964:
3962:
3961:
3956:
3928:
3926:
3925:
3920:
3908:
3906:
3905:
3900:
3898:
3894:
3866:
3864:
3863:
3858:
3856:
3832:
3830:
3829:
3824:
3822:
3821:
3805:
3803:
3802:
3797:
3785:
3783:
3782:
3777:
3765:
3763:
3762:
3757:
3755:
3751:
3738:
3737:
3728:
3727:
3702:
3700:
3699:
3694:
3692:
3688:
3675:
3674:
3665:
3664:
3655:
3654:
3562:regular grammars
3525:
3521:
3517:
3513:
3511:
3510:
3505:
3500:
3475:
3473:
3472:
3467:
3465:
3449:
3432:
3413:
3393:
3380:
3361:
3347:
3325:
3308:
3280:
3269:
3256:
3246:
3223:
3210:
3203:
3183:
3173:
3159:
3145:
3128:
3126:
3125:
3120:
3118:
3108:
3094:
3081:
3068:
3057:
3044:
3037:
3020:
3007:
3003:
2989:
2975:
2958:
2956:
2955:
2950:
2948:
2937:
2927:
2911:
2909:
2908:
2903:
2879:
2877:
2876:
2871:
2859:
2857:
2856:
2851:
2839:
2837:
2836:
2831:
2819:
2817:
2816:
2811:
2795:
2793:
2792:
2787:
2785:
2784:
2768:
2766:
2765:
2760:
2758:
2754:
2741:
2740:
2731:
2730:
2721:
2720:
2681:
2679:
2678:
2673:
2647:
2645:
2644:
2639:
2613:
2611:
2610:
2605:
2579:
2577:
2576:
2571:
2540:
2538:
2537:
2532:
2520:
2518:
2517:
2512:
2500:
2498:
2497:
2492:
2490:
2486:
2452:
2450:
2449:
2444:
2442:
2438:
2410:
2408:
2407:
2402:
2373:
2371:
2370:
2365:
2349:
2347:
2346:
2341:
2311:semi-Thue system
2308:
2306:
2305:
2300:
2254:
2252:
2251:
2246:
2234:
2232:
2231:
2226:
2215:
2203:
2201:
2200:
2195:
2172:
2170:
2169:
2164:
2162:
2161:
2145:
2143:
2142:
2137:
2135:
2131:
2127:
2114:
2106:
2105:
2066:
2064:
2063:
2058:
2046:
2044:
2043:
2038:
2036:
2035:
2001:
1999:
1998:
1993:
1991:
1966:
1964:
1963:
1958:
1956:
1943:
1930:
1928:
1927:
1922:
1848:
1847:
1791:
1769:
1767:
1766:
1761:
1759:
1758:
1730:
1728:
1727:
1722:
1720:
1703:
1701:
1700:
1695:
1654:Given a grammar
1636:rewriting system
1633:
1631:
1630:
1625:
1574:
1572:
1571:
1566:
1543:
1541:
1540:
1535:
1519:
1517:
1516:
1511:
1491:
1489:
1488:
1483:
1467:
1465:
1464:
1459:
1457:
1441:
1439:
1438:
1433:
1431:
1430:
1406:
1405:
1381:
1380:
1345:production rules
1325:terminal symbols
1321:
1319:
1318:
1313:
1249:
1247:
1246:
1241:
1221:
1219:
1218:
1213:
1193:
1191:
1190:
1185:
1162:
1160:
1159:
1154:
1122:
1120:
1119:
1114:
1102:
1100:
1099:
1094:
1082:
1080:
1079:
1074:
1062:
1060:
1059:
1054:
1042:
1040:
1039:
1034:
1016:
1014:
1013:
1008:
996:
994:
993:
988:
976:
974:
973:
968:
956:
954:
953:
948:
933:
931:
930:
925:
910:
908:
907:
902:
876:
874:
873:
868:
845:
843:
842:
837:
812:Examples 2 and 3
803:
801:
800:
795:
783:
781:
780:
775:
763:
761:
760:
755:
743:
741:
740:
735:
733:
732:
716:
714:
713:
708:
607:
606:
591:
590:
568:
566:
565:
560:
462:
460:
459:
454:
431:
429:
428:
423:
348:semi-Thue system
332:production rules
275:formal semantics
256:production rules
224:
217:
210:
53:Formal languages
38:
21:
7418:
7417:
7413:
7412:
7411:
7409:
7408:
7407:
7373:
7372:
7371:
7366:
7355:
7348:
7293:Category theory
7283:Algebraic logic
7266:
7237:Lambda calculus
7175:Church encoding
7161:
7137:Truth predicate
6993:
6959:Complete theory
6882:
6751:
6747:
6743:
6738:
6730:
6450: and
6446:
6441:
6427:
6403:New Foundations
6371:axiom of choice
6354:
6316:Gödel numbering
6256: and
6248:
6152:
6037:
5987:
5968:
5917:Boolean algebra
5903:
5867:Equiconsistency
5832:Classical logic
5809:
5790:Halting problem
5778: and
5754: and
5742: and
5741:
5736:Theorems (
5731:
5648:
5643:
5613:
5608:
5605:
5598:
5592:
5587:
5509:
5453:
5432:
5378:
5359:
5282:
5280:formal grammars
5272:Automata theory
5269:
5239:
5234:
5233:
5222:
5218:
5209:
5205:
5196:
5192:
5181:
5177:
5163:
5162:
5158:
5149:Wayback Machine
5140:
5136:
5127:
5123:
5110:
5106:
5097:
5093:
5076:
5072:
5047:
5046:
5042:
5032:Wayback Machine
5022:
5018:
5009:
5005:
4999:Wayback Machine
4990:
4986:
4979:
4963:
4962:
4958:
4951:
4935:
4934:
4930:
4916:
4915:
4911:
4879:
4878:
4871:
4860:
4845:
4844:
4840:
4835:
4830:
4756:
4691:
4659:
4652:
4621:
4584:
4583:
4553:
4552:
4523:
4522:
4493:
4492:
4463:
4462:
4433:
4432:
4408:
4407:
4381:
4377:
4366:
4365:
4333:
4329:
4318:
4317:
4296:
4291:
4290:
4271:
4270:
4251:
4250:
4206:
4196:
4195:
4191:
4186:
4185:
4147:
4137:
4136:
4132:
4127:
4126:
4112:
4084:
4083:
4059:
4048:
4047:
4012:
4001:
4000:
3969:
3968:
3935:
3934:
3911:
3910:
3884:
3880:
3869:
3868:
3846:
3835:
3834:
3813:
3808:
3807:
3788:
3787:
3768:
3767:
3729:
3719:
3718:
3714:
3709:
3708:
3666:
3656:
3646:
3645:
3641:
3621:
3620:
3603:
3543:
3535:Main articles:
3533:
3523:
3519:
3515:
3483:
3482:
3478:
3463:
3462:
3378:
3377:
3254:
3253:
3208:
3207:
3146:
3132:
3131:
3116:
3115:
3079:
3078:
3042:
3041:
3005:
3004:
2976:
2962:
2961:
2918:
2917:
2885:
2884:
2862:
2861:
2842:
2841:
2822:
2821:
2802:
2801:
2776:
2771:
2770:
2732:
2722:
2712:
2711:
2707:
2687:
2686:
2652:
2651:
2618:
2617:
2584:
2583:
2547:
2546:
2523:
2522:
2503:
2502:
2470:
2466:
2455:
2454:
2428:
2424:
2413:
2412:
2393:
2392:
2380:
2356:
2355:
2314:
2313:
2261:
2260:
2237:
2236:
2206:
2205:
2186:
2185:
2153:
2148:
2147:
2097:
2078:
2074:
2069:
2068:
2049:
2048:
2027:
2010:
2009:
2008:is a member of
2006:sentential form
1977:
1976:
1967:(pronounced as
1937:
1936:
1839:
1774:
1773:
1770:is defined by:
1750:
1733:
1732:
1706:
1705:
1656:
1655:
1648:
1592:
1591:
1581:sentence symbol
1551:
1550:
1526:
1525:
1502:
1501:
1474:
1473:
1448:
1447:
1422:
1397:
1372:
1355:
1354:
1304:
1303:
1267:
1262:
1256:
1226:
1225:
1198:
1197:
1167:
1166:
1136:
1135:
1105:
1104:
1085:
1084:
1065:
1064:
1045:
1044:
1019:
1018:
999:
998:
979:
978:
959:
958:
939:
938:
916:
915:
881:
880:
850:
849:
822:
821:
814:
786:
785:
766:
765:
746:
745:
724:
719:
718:
598:
582:
574:
573:
500:
499:
436:
435:
402:
401:
394:
341:right-hand side
327:
295:automata theory
244:formal language
228:
199:
198:
184:Syntax analysis
159:Predicate logic
144:
143:
134:
133:
109:Automata theory
64:
63:
36:
23:
22:
18:Sentential form
15:
12:
11:
5:
7416:
7414:
7406:
7405:
7400:
7395:
7390:
7385:
7375:
7374:
7368:
7367:
7353:
7350:
7349:
7347:
7346:
7341:
7336:
7331:
7326:
7325:
7324:
7314:
7309:
7304:
7295:
7290:
7285:
7280:
7278:Abstract logic
7274:
7272:
7268:
7267:
7265:
7264:
7259:
7257:Turing machine
7254:
7249:
7244:
7239:
7234:
7229:
7228:
7227:
7222:
7217:
7212:
7207:
7197:
7195:Computable set
7192:
7187:
7182:
7177:
7171:
7169:
7163:
7162:
7160:
7159:
7154:
7149:
7144:
7139:
7134:
7129:
7124:
7123:
7122:
7117:
7112:
7102:
7097:
7092:
7090:Satisfiability
7087:
7082:
7077:
7076:
7075:
7065:
7064:
7063:
7053:
7052:
7051:
7046:
7041:
7036:
7031:
7021:
7020:
7019:
7014:
7007:Interpretation
7003:
7001:
6995:
6994:
6992:
6991:
6986:
6981:
6976:
6971:
6961:
6956:
6955:
6954:
6953:
6952:
6942:
6937:
6927:
6922:
6917:
6912:
6907:
6902:
6896:
6894:
6888:
6887:
6884:
6883:
6881:
6880:
6872:
6871:
6870:
6869:
6864:
6863:
6862:
6857:
6852:
6832:
6831:
6830:
6828:minimal axioms
6825:
6814:
6813:
6812:
6801:
6800:
6799:
6794:
6789:
6784:
6779:
6774:
6761:
6759:
6740:
6739:
6737:
6736:
6735:
6734:
6722:
6717:
6716:
6715:
6710:
6705:
6700:
6690:
6685:
6680:
6675:
6674:
6673:
6668:
6658:
6657:
6656:
6651:
6646:
6641:
6631:
6626:
6625:
6624:
6619:
6614:
6604:
6603:
6602:
6597:
6592:
6587:
6582:
6577:
6567:
6562:
6557:
6552:
6551:
6550:
6545:
6540:
6535:
6525:
6520:
6518:Formation rule
6515:
6510:
6509:
6508:
6503:
6493:
6492:
6491:
6481:
6476:
6471:
6466:
6460:
6454:
6437:Formal systems
6433:
6432:
6429:
6428:
6426:
6425:
6420:
6415:
6410:
6405:
6400:
6395:
6390:
6385:
6380:
6379:
6378:
6373:
6362:
6360:
6356:
6355:
6353:
6352:
6351:
6350:
6340:
6335:
6334:
6333:
6326:Large cardinal
6323:
6318:
6313:
6308:
6303:
6289:
6288:
6287:
6282:
6277:
6262:
6260:
6250:
6249:
6247:
6246:
6245:
6244:
6239:
6234:
6224:
6219:
6214:
6209:
6204:
6199:
6194:
6189:
6184:
6179:
6174:
6169:
6163:
6161:
6154:
6153:
6151:
6150:
6149:
6148:
6143:
6138:
6133:
6128:
6123:
6115:
6114:
6113:
6108:
6098:
6093:
6091:Extensionality
6088:
6086:Ordinal number
6083:
6073:
6068:
6067:
6066:
6055:
6049:
6043:
6042:
6039:
6038:
6036:
6035:
6030:
6025:
6020:
6015:
6010:
6005:
6004:
6003:
5993:
5992:
5991:
5978:
5976:
5970:
5969:
5967:
5966:
5965:
5964:
5959:
5954:
5944:
5939:
5934:
5929:
5924:
5919:
5913:
5911:
5905:
5904:
5902:
5901:
5896:
5891:
5886:
5881:
5876:
5871:
5870:
5869:
5859:
5854:
5849:
5844:
5839:
5834:
5828:
5826:
5817:
5811:
5810:
5808:
5807:
5802:
5797:
5792:
5787:
5782:
5770:Cantor's
5768:
5763:
5758:
5748:
5746:
5733:
5732:
5730:
5729:
5724:
5719:
5714:
5709:
5704:
5699:
5694:
5689:
5684:
5679:
5674:
5669:
5668:
5667:
5656:
5654:
5650:
5649:
5644:
5642:
5641:
5634:
5627:
5619:
5610:
5609:
5597:
5594:
5593:
5589:
5588:
5586:
5585:
5583:Acyclic finite
5580:
5575:
5570:
5565:
5560:
5555:
5550:
5544:
5539:
5534:
5533:Turing Machine
5528:
5526:Linear-bounded
5523:
5518:
5516:Turing machine
5512:
5510:
5508:
5507:
5502:
5497:
5492:
5487:
5482:
5477:
5475:Tree-adjoining
5472:
5467:
5464:
5459:
5451:
5446:
5441:
5435:
5433:
5431:
5430:
5425:
5422:
5417:
5412:
5407:
5402:
5400:Tree-adjoining
5397:
5392:
5389:
5384:
5376:
5371:
5368:
5362:
5360:
5358:
5357:
5354:
5351:
5348:
5345:
5342:
5339:
5336:
5333:
5330:
5327:
5324:
5321:
5318:
5314:
5311:
5310:
5305:
5300:
5295:
5287:
5284:
5283:
5270:
5268:
5267:
5260:
5253:
5245:
5238:
5237:External links
5235:
5232:
5231:
5216:
5203:
5190:
5175:
5156:
5134:
5121:
5104:
5091:
5070:
5059:(6): 607–639.
5040:
5023:Earley, Jay, "
5016:
5003:
4984:
4977:
4956:
4949:
4928:
4909:
4890:(3): 113–124.
4869:
4858:
4837:
4836:
4834:
4831:
4829:
4828:
4823:
4818:
4813:
4808:
4803:
4798:
4793:
4788:
4783:
4778:
4773:
4768:
4763:
4757:
4755:
4752:
4751:
4750:
4739:expressiveness
4732:
4722:
4701:by means of a
4690:
4687:
4671:left-recursive
4651:
4648:
4647:
4646:
4639:Affix grammars
4636:
4620:
4617:
4600:
4597:
4594:
4591:
4580:
4579:
4578:
4577:
4566:
4563:
4560:
4550:
4539:
4536:
4533:
4530:
4520:
4509:
4506:
4503:
4500:
4490:
4479:
4476:
4473:
4470:
4460:
4449:
4446:
4443:
4440:
4415:
4394:
4390:
4387:
4384:
4380:
4376:
4373:
4352:
4348:
4345:
4342:
4339:
4336:
4332:
4328:
4325:
4303:
4299:
4278:
4258:
4237:
4233:
4230:
4227:
4224:
4221:
4218:
4213:
4209:
4203:
4199:
4194:
4172:
4168:
4165:
4162:
4159:
4154:
4150:
4144:
4140:
4135:
4111:
4108:
4091:
4071:
4066:
4062:
4058:
4055:
4040:Big O notation
4024:
4019:
4015:
4011:
4008:
3997:
3996:
3985:
3982:
3979:
3976:
3965:
3954:
3951:
3948:
3945:
3942:
3918:
3897:
3893:
3890:
3887:
3883:
3879:
3876:
3855:
3852:
3849:
3845:
3842:
3820:
3816:
3795:
3775:
3754:
3750:
3747:
3744:
3741:
3736:
3732:
3726:
3722:
3717:
3691:
3687:
3684:
3681:
3678:
3673:
3669:
3663:
3659:
3653:
3649:
3644:
3640:
3637:
3634:
3631:
3628:
3602:
3599:
3583:Turing machine
3532:
3529:
3528:
3527:
3514:reads "String
3503:
3498:
3495:
3490:
3481:(On notation:
3477:
3476:
3461:
3458:
3455:
3452:
3448:
3445:
3441:
3438:
3435:
3430:
3427:
3422:
3419:
3416:
3412:
3409:
3405:
3402:
3399:
3396:
3391:
3388:
3383:
3381:
3379:
3376:
3373:
3370:
3367:
3364:
3360:
3357:
3353:
3350:
3345:
3342:
3337:
3334:
3331:
3328:
3324:
3321:
3317:
3314:
3311:
3306:
3303:
3298:
3295:
3292:
3289:
3286:
3283:
3279:
3276:
3272:
3267:
3264:
3259:
3257:
3255:
3252:
3249:
3245:
3242:
3239:
3235:
3232:
3229:
3226:
3221:
3218:
3213:
3211:
3209:
3206:
3202:
3199:
3196:
3193:
3189:
3186:
3181:
3178:
3172:
3169:
3166:
3163:
3157:
3154:
3149:
3147:
3144:
3140:
3139:
3129:
3114:
3111:
3107:
3104:
3100:
3097:
3092:
3089:
3084:
3082:
3080:
3077:
3074:
3071:
3067:
3064:
3060:
3055:
3052:
3047:
3045:
3043:
3040:
3036:
3033:
3030:
3026:
3023:
3018:
3015:
3010:
3008:
3006:
3002:
2999:
2996:
2993:
2987:
2984:
2979:
2977:
2974:
2970:
2969:
2959:
2947:
2944:
2941:
2935:
2932:
2926:
2914:
2901:
2898:
2895:
2892:
2869:
2849:
2829:
2809:
2783:
2779:
2757:
2753:
2750:
2747:
2744:
2739:
2735:
2729:
2725:
2719:
2715:
2710:
2706:
2703:
2700:
2697:
2694:
2683:
2682:
2671:
2668:
2665:
2662:
2659:
2648:
2637:
2634:
2631:
2628:
2625:
2614:
2603:
2600:
2597:
2594:
2591:
2580:
2569:
2566:
2563:
2560:
2557:
2554:
2530:
2510:
2489:
2485:
2482:
2479:
2476:
2473:
2469:
2465:
2462:
2441:
2437:
2434:
2431:
2427:
2423:
2420:
2400:
2379:
2376:
2363:
2339:
2336:
2333:
2330:
2327:
2324:
2321:
2298:
2295:
2292:
2289:
2286:
2283:
2280:
2277:
2274:
2271:
2268:
2257:
2256:
2244:
2224:
2221:
2218:
2214:
2193:
2178:
2173:) is called a
2160:
2156:
2134:
2130:
2125:
2121:
2118:
2112:
2109:
2104:
2100:
2096:
2093:
2090:
2087:
2084:
2081:
2077:
2056:
2034:
2030:
2026:
2023:
2020:
2017:
2002:
1989:
1986:
1954:
1950:
1947:
1933:
1932:
1931:
1920:
1917:
1914:
1911:
1908:
1905:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1872:
1869:
1866:
1863:
1860:
1857:
1854:
1851:
1846:
1842:
1838:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1814:
1811:
1808:
1805:
1802:
1798:
1794:
1789:
1786:
1781:
1757:
1753:
1749:
1746:
1743:
1740:
1718:
1715:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1647:
1644:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1585:
1584:
1564:
1561:
1558:
1546:
1545:
1533:
1509:
1481:
1456:
1444:
1443:
1442:
1429:
1425:
1421:
1418:
1415:
1412:
1409:
1404:
1400:
1396:
1393:
1390:
1387:
1384:
1379:
1375:
1371:
1368:
1365:
1362:
1349:
1348:
1337:
1311:
1300:
1266:
1263:
1258:Main article:
1255:
1252:
1251:
1250:
1239:
1236:
1233:
1222:
1211:
1208:
1205:
1194:
1183:
1180:
1177:
1174:
1163:
1152:
1149:
1146:
1143:
1123:as we please.
1112:
1092:
1072:
1052:
1032:
1029:
1026:
1006:
986:
966:
946:
923:
912:
911:
900:
897:
894:
891:
888:
877:
866:
863:
860:
857:
846:
835:
832:
829:
813:
810:
793:
773:
753:
731:
727:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
605:
601:
597:
594:
589:
585:
581:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
464:
463:
452:
449:
446:
443:
432:
421:
418:
415:
412:
409:
393:
390:
337:left-hand side
326:
323:
315:deep structure
236:formal grammar
230:
229:
227:
226:
219:
212:
204:
201:
200:
197:
196:
191:
186:
181:
176:
171:
166:
161:
156:
151:
149:Formal methods
145:
141:
140:
139:
136:
135:
132:
131:
129:Atomic formula
126:
121:
116:
111:
106:
101:
99:Formation rule
96:
94:Formal grammar
91:
86:
81:
76:
71:
65:
61:
60:
59:
56:
55:
49:
48:
34:
24:
14:
13:
10:
9:
6:
4:
3:
2:
7415:
7404:
7401:
7399:
7396:
7394:
7391:
7389:
7386:
7384:
7381:
7380:
7378:
7365:
7364:
7359:
7351:
7345:
7342:
7340:
7337:
7335:
7332:
7330:
7327:
7323:
7320:
7319:
7318:
7315:
7313:
7310:
7308:
7305:
7303:
7299:
7296:
7294:
7291:
7289:
7286:
7284:
7281:
7279:
7276:
7275:
7273:
7269:
7263:
7260:
7258:
7255:
7253:
7252:Recursive set
7250:
7248:
7245:
7243:
7240:
7238:
7235:
7233:
7230:
7226:
7223:
7221:
7218:
7216:
7213:
7211:
7208:
7206:
7203:
7202:
7201:
7198:
7196:
7193:
7191:
7188:
7186:
7183:
7181:
7178:
7176:
7173:
7172:
7170:
7168:
7164:
7158:
7155:
7153:
7150:
7148:
7145:
7143:
7140:
7138:
7135:
7133:
7130:
7128:
7125:
7121:
7118:
7116:
7113:
7111:
7108:
7107:
7106:
7103:
7101:
7098:
7096:
7093:
7091:
7088:
7086:
7083:
7081:
7078:
7074:
7071:
7070:
7069:
7066:
7062:
7061:of arithmetic
7059:
7058:
7057:
7054:
7050:
7047:
7045:
7042:
7040:
7037:
7035:
7032:
7030:
7027:
7026:
7025:
7022:
7018:
7015:
7013:
7010:
7009:
7008:
7005:
7004:
7002:
7000:
6996:
6990:
6987:
6985:
6982:
6980:
6977:
6975:
6972:
6969:
6968:from ZFC
6965:
6962:
6960:
6957:
6951:
6948:
6947:
6946:
6943:
6941:
6938:
6936:
6933:
6932:
6931:
6928:
6926:
6923:
6921:
6918:
6916:
6913:
6911:
6908:
6906:
6903:
6901:
6898:
6897:
6895:
6893:
6889:
6879:
6878:
6874:
6873:
6868:
6867:non-Euclidean
6865:
6861:
6858:
6856:
6853:
6851:
6850:
6846:
6845:
6843:
6840:
6839:
6837:
6833:
6829:
6826:
6824:
6821:
6820:
6819:
6815:
6811:
6808:
6807:
6806:
6802:
6798:
6795:
6793:
6790:
6788:
6785:
6783:
6780:
6778:
6775:
6773:
6770:
6769:
6767:
6763:
6762:
6760:
6755:
6749:
6744:Example
6741:
6733:
6728:
6727:
6726:
6723:
6721:
6718:
6714:
6711:
6709:
6706:
6704:
6701:
6699:
6696:
6695:
6694:
6691:
6689:
6686:
6684:
6681:
6679:
6676:
6672:
6669:
6667:
6664:
6663:
6662:
6659:
6655:
6652:
6650:
6647:
6645:
6642:
6640:
6637:
6636:
6635:
6632:
6630:
6627:
6623:
6620:
6618:
6615:
6613:
6610:
6609:
6608:
6605:
6601:
6598:
6596:
6593:
6591:
6588:
6586:
6583:
6581:
6578:
6576:
6573:
6572:
6571:
6568:
6566:
6563:
6561:
6558:
6556:
6553:
6549:
6546:
6544:
6541:
6539:
6536:
6534:
6531:
6530:
6529:
6526:
6524:
6521:
6519:
6516:
6514:
6511:
6507:
6504:
6502:
6501:by definition
6499:
6498:
6497:
6494:
6490:
6487:
6486:
6485:
6482:
6480:
6477:
6475:
6472:
6470:
6467:
6465:
6462:
6461:
6458:
6455:
6453:
6449:
6444:
6438:
6434:
6424:
6421:
6419:
6416:
6414:
6411:
6409:
6406:
6404:
6401:
6399:
6396:
6394:
6391:
6389:
6388:Kripke–Platek
6386:
6384:
6381:
6377:
6374:
6372:
6369:
6368:
6367:
6364:
6363:
6361:
6357:
6349:
6346:
6345:
6344:
6341:
6339:
6336:
6332:
6329:
6328:
6327:
6324:
6322:
6319:
6317:
6314:
6312:
6309:
6307:
6304:
6301:
6297:
6293:
6290:
6286:
6283:
6281:
6278:
6276:
6273:
6272:
6271:
6267:
6264:
6263:
6261:
6259:
6255:
6251:
6243:
6240:
6238:
6235:
6233:
6232:constructible
6230:
6229:
6228:
6225:
6223:
6220:
6218:
6215:
6213:
6210:
6208:
6205:
6203:
6200:
6198:
6195:
6193:
6190:
6188:
6185:
6183:
6180:
6178:
6175:
6173:
6170:
6168:
6165:
6164:
6162:
6160:
6155:
6147:
6144:
6142:
6139:
6137:
6134:
6132:
6129:
6127:
6124:
6122:
6119:
6118:
6116:
6112:
6109:
6107:
6104:
6103:
6102:
6099:
6097:
6094:
6092:
6089:
6087:
6084:
6082:
6078:
6074:
6072:
6069:
6065:
6062:
6061:
6060:
6057:
6056:
6053:
6050:
6048:
6044:
6034:
6031:
6029:
6026:
6024:
6021:
6019:
6016:
6014:
6011:
6009:
6006:
6002:
5999:
5998:
5997:
5994:
5990:
5985:
5984:
5983:
5980:
5979:
5977:
5975:
5971:
5963:
5960:
5958:
5955:
5953:
5950:
5949:
5948:
5945:
5943:
5940:
5938:
5935:
5933:
5930:
5928:
5925:
5923:
5920:
5918:
5915:
5914:
5912:
5910:
5909:Propositional
5906:
5900:
5897:
5895:
5892:
5890:
5887:
5885:
5882:
5880:
5877:
5875:
5872:
5868:
5865:
5864:
5863:
5860:
5858:
5855:
5853:
5850:
5848:
5845:
5843:
5840:
5838:
5837:Logical truth
5835:
5833:
5830:
5829:
5827:
5825:
5821:
5818:
5816:
5812:
5806:
5803:
5801:
5798:
5796:
5793:
5791:
5788:
5786:
5783:
5781:
5777:
5773:
5769:
5767:
5764:
5762:
5759:
5757:
5753:
5750:
5749:
5747:
5745:
5739:
5734:
5728:
5725:
5723:
5720:
5718:
5715:
5713:
5710:
5708:
5705:
5703:
5700:
5698:
5695:
5693:
5690:
5688:
5685:
5683:
5680:
5678:
5675:
5673:
5670:
5666:
5663:
5662:
5661:
5658:
5657:
5655:
5651:
5647:
5640:
5635:
5633:
5628:
5626:
5621:
5620:
5617:
5602:
5601:proper subset
5595:
5584:
5581:
5579:
5576:
5574:
5571:
5569:
5566:
5564:
5561:
5559:
5556:
5554:
5551:
5549:
5545:
5543:
5540:
5538:
5535:
5532:
5529:
5527:
5524:
5522:
5519:
5517:
5514:
5513:
5511:
5506:
5503:
5501:
5498:
5496:
5493:
5491:
5488:
5486:
5483:
5481:
5478:
5476:
5473:
5471:
5468:
5465:
5463:
5460:
5457:
5452:
5450:
5447:
5445:
5442:
5440:
5437:
5436:
5434:
5429:
5428:Non-recursive
5426:
5423:
5421:
5418:
5416:
5413:
5411:
5408:
5406:
5403:
5401:
5398:
5396:
5393:
5390:
5388:
5385:
5382:
5377:
5375:
5372:
5369:
5367:
5364:
5363:
5361:
5355:
5352:
5349:
5346:
5343:
5340:
5337:
5334:
5331:
5328:
5325:
5322:
5319:
5316:
5315:
5313:
5312:
5309:
5306:
5304:
5301:
5299:
5296:
5294:
5291:
5290:
5285:
5281:
5277:
5273:
5266:
5261:
5259:
5254:
5252:
5247:
5246:
5243:
5236:
5228:
5227:
5223:Ford, Bryan,
5220:
5217:
5213:
5207:
5204:
5200:
5194:
5191:
5187:
5186:
5179:
5176:
5171:
5167:
5160:
5157:
5154:
5150:
5146:
5143:
5138:
5135:
5131:
5125:
5122:
5118:
5114:
5108:
5105:
5101:
5095:
5092:
5088:
5084:
5080:
5074:
5071:
5066:
5062:
5058:
5054:
5050:
5044:
5041:
5037:
5033:
5029:
5026:
5020:
5017:
5013:
5007:
5004:
5000:
4996:
4993:
4988:
4985:
4980:
4974:
4970:
4966:
4960:
4957:
4952:
4946:
4942:
4938:
4932:
4929:
4924:
4921:. The Hague:
4920:
4913:
4910:
4905:
4901:
4897:
4893:
4889:
4885:
4884:
4876:
4874:
4870:
4866:
4861:
4859:9781466513457
4855:
4851:
4850:
4842:
4839:
4832:
4827:
4824:
4822:
4821:Shape grammar
4819:
4817:
4814:
4812:
4809:
4807:
4804:
4802:
4799:
4797:
4794:
4792:
4789:
4787:
4784:
4782:
4779:
4777:
4774:
4772:
4769:
4767:
4764:
4762:
4759:
4758:
4753:
4748:
4744:
4740:
4736:
4733:
4730:
4726:
4725:Link grammars
4723:
4720:
4716:
4713:
4712:
4711:
4707:
4704:
4700:
4696:
4688:
4686:
4684:
4680:
4676:
4672:
4668:
4664:
4657:
4649:
4644:
4640:
4637:
4634:
4630:
4627:
4626:
4625:
4618:
4616:
4614:
4595:
4589:
4564:
4558:
4551:
4537:
4534:
4528:
4521:
4507:
4504:
4498:
4491:
4477:
4474:
4468:
4461:
4447:
4444:
4438:
4431:
4430:
4429:
4428:
4427:
4413:
4392:
4388:
4385:
4382:
4378:
4374:
4350:
4346:
4343:
4340:
4337:
4334:
4330:
4326:
4323:
4301:
4297:
4276:
4256:
4235:
4231:
4228:
4225:
4222:
4219:
4216:
4211:
4207:
4201:
4197:
4192:
4170:
4166:
4163:
4160:
4157:
4152:
4148:
4142:
4138:
4133:
4125:The language
4123:
4121:
4117:
4109:
4107:
4105:
4089:
4064:
4060:
4053:
4045:
4041:
4038:
4017:
4013:
4006:
3983:
3980:
3974:
3966:
3952:
3949:
3946:
3940:
3932:
3931:
3930:
3916:
3895:
3891:
3888:
3885:
3881:
3877:
3853:
3850:
3847:
3843:
3840:
3818:
3814:
3793:
3773:
3752:
3748:
3745:
3742:
3739:
3734:
3730:
3724:
3720:
3715:
3706:
3689:
3685:
3682:
3679:
3676:
3671:
3667:
3661:
3657:
3651:
3647:
3642:
3638:
3632:
3626:
3619:The language
3617:
3615:
3610:
3609:
3600:
3598:
3596:
3592:
3588:
3584:
3580:
3576:
3575:
3570:
3569:
3564:
3563:
3559:(Type 2) and
3558:
3557:
3552:
3548:
3542:
3538:
3530:
3501:
3496:
3488:
3480:
3479:
3459:
3456:
3453:
3450:
3439:
3436:
3433:
3428:
3420:
3417:
3414:
3403:
3400:
3397:
3394:
3389:
3382:
3374:
3371:
3368:
3365:
3362:
3351:
3348:
3343:
3335:
3332:
3329:
3326:
3315:
3312:
3309:
3304:
3296:
3293:
3290:
3287:
3284:
3281:
3270:
3265:
3258:
3250:
3247:
3233:
3230:
3227:
3224:
3219:
3212:
3204:
3187:
3184:
3179:
3155:
3148:
3130:
3112:
3109:
3098:
3095:
3090:
3083:
3075:
3072:
3069:
3058:
3053:
3046:
3038:
3024:
3021:
3016:
3009:
2985:
2978:
2960:
2933:
2916:
2915:
2913:
2896:
2890:
2881:
2867:
2847:
2827:
2807:
2799:
2781:
2777:
2755:
2751:
2748:
2745:
2742:
2737:
2733:
2727:
2723:
2717:
2713:
2708:
2704:
2698:
2692:
2669:
2666:
2660:
2657:
2649:
2635:
2632:
2626:
2623:
2615:
2601:
2598:
2595:
2589:
2581:
2567:
2564:
2561:
2558:
2552:
2544:
2543:
2542:
2528:
2508:
2487:
2483:
2480:
2477:
2474:
2471:
2467:
2463:
2439:
2435:
2432:
2429:
2425:
2421:
2418:
2398:
2389:
2388:
2386:
2377:
2375:
2361:
2353:
2334:
2331:
2325:
2322:
2312:
2293:
2290:
2287:
2284:
2278:
2275:
2269:
2266:
2242:
2219:
2204:, denoted as
2191:
2183:
2179:
2176:
2158:
2132:
2128:
2123:
2119:
2110:
2107:
2102:
2094:
2091:
2082:
2079:
2075:
2054:
2032:
2024:
2021:
2007:
2003:
1987:
1974:
1970:
1952:
1948:
1935:the relation
1934:
1915:
1912:
1909:
1906:
1903:
1897:
1891:
1888:
1885:
1879:
1873:
1867:
1864:
1861:
1858:
1855:
1849:
1844:
1836:
1833:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1792:
1787:
1779:
1772:
1771:
1755:
1747:
1744:
1716:
1688:
1685:
1682:
1679:
1673:
1670:
1664:
1661:
1653:
1652:
1651:
1645:
1643:
1641:
1637:
1618:
1615:
1612:
1609:
1603:
1600:
1590:
1582:
1578:
1562:
1559:
1556:
1548:
1547:
1531:
1523:
1499:
1495:
1479:
1472:operator and
1471:
1454:
1445:
1427:
1419:
1416:
1402:
1394:
1391:
1382:
1377:
1369:
1366:
1353:
1352:
1351:
1350:
1346:
1342:
1339:A finite set
1338:
1335:
1331:
1327:
1326:
1302:A finite set
1301:
1298:
1294:
1290:
1289:
1284:
1281:A finite set
1280:
1279:
1278:
1276:
1272:
1264:
1261:
1253:
1237:
1231:
1223:
1209:
1203:
1195:
1181:
1178:
1172:
1164:
1150:
1147:
1141:
1133:
1132:
1131:
1129:
1124:
1110:
1090:
1070:
1050:
1030:
1027:
1024:
1004:
984:
964:
944:
935:
921:
898:
892:
889:
886:
878:
864:
861:
855:
847:
833:
827:
819:
818:
817:
811:
809:
807:
791:
771:
751:
729:
725:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
623:
617:
614:
611:
608:
603:
599:
595:
592:
587:
583:
570:
556:
553:
550:
547:
544:
541:
535:
532:
529:
526:
523:
517:
514:
511:
505:
497:
493:
489:
485:
481:
477:
473:
469:
450:
447:
441:
433:
419:
416:
413:
407:
399:
398:
397:
391:
389:
387:
383:
379:
374:
372:
366:
364:
360:
358:
354:
349:
344:
342:
338:
334:
333:
324:
322:
320:
316:
312:
308:
304:
300:
296:
292:
287:
282:
280:
276:
272:
268:
264:
259:
257:
253:
249:
245:
241:
237:
225:
220:
218:
213:
211:
206:
205:
203:
202:
195:
192:
190:
187:
185:
182:
180:
177:
175:
172:
170:
167:
165:
162:
160:
157:
155:
152:
150:
147:
146:
138:
137:
130:
127:
125:
122:
120:
117:
115:
112:
110:
107:
105:
102:
100:
97:
95:
92:
90:
87:
85:
82:
80:
77:
75:
72:
70:
69:Formal system
67:
66:
58:
57:
54:
50:
46:
45:
40:
39:
29:
19:
7354:
7152:Ultraproduct
6999:Model theory
6964:Independence
6900:Formal proof
6892:Proof theory
6875:
6848:
6805:real numbers
6777:second-order
6688:Substitution
6565:Metalanguage
6522:
6506:conservative
6479:Axiom schema
6423:Constructive
6393:Morse–Kelley
6359:Set theories
6338:Aleph number
6331:inaccessible
6237:Grothendieck
6121:intersection
6008:Higher-order
5996:Second-order
5942:Truth tables
5899:Venn diagram
5682:Formal proof
5537:Nested stack
5480:Context-free
5405:Context-free
5366:Unrestricted
5297:
5279:
5224:
5219:
5211:
5206:
5193:
5183:
5178:
5169:
5159:
5137:
5129:
5124:
5116:
5107:
5099:
5094:
5086:
5078:
5073:
5056:
5052:
5049:Knuth, D. E.
5043:
5035:
5019:
5011:
5006:
4987:
4968:
4959:
4940:
4931:
4918:
4912:
4887:
4881:
4848:
4841:
4708:
4702:
4698:
4692:
4678:
4674:
4660:
4622:
4581:
4249:(at least 1
4124:
4113:
4036:
3998:
3766:(at least 1
3618:
3613:
3606:
3604:
3572:
3566:
3560:
3554:
3547:Noam Chomsky
3544:
2882:
2800:consecutive
2797:
2684:
2390:
2382:
2381:
2351:
2259:The grammar
2258:
2181:
2174:
2005:
1968:
1649:
1586:
1580:
1577:start symbol
1576:
1575:that is the
1521:
1498:empty string
1344:
1340:
1333:
1323:
1296:
1286:
1282:
1274:
1271:Noam Chomsky
1268:
1125:
936:
913:
815:
806:context-free
571:
495:
491:
487:
483:
479:
475:
471:
467:
465:
395:
385:
381:
377:
375:
367:
363:start symbol
362:
356:
352:
345:
340:
336:
330:
328:
283:
260:
235:
233:
142:Applications
93:
62:Key concepts
43:
7262:Type theory
7210:undecidable
7142:Truth value
7029:equivalence
6708:non-logical
6321:Enumeration
6311:Isomorphism
6258:cardinality
6242:Von Neumann
6207:Ultrafilter
6172:Uncountable
6106:equivalence
6023:Quantifiers
6013:Fixed-point
5982:First-order
5862:Consistency
5847:Proposition
5824:Traditional
5795:Lindström's
5785:Compactness
5727:Type theory
5672:Cardinality
5546:restricted
4729:linguistics
4633:parse trees
2352:nonterminal
1470:Kleene star
784:times (and
353:nonterminal
7377:Categories
7073:elementary
6766:arithmetic
6634:Quantifier
6612:functional
6484:Expression
6202:Transitive
6146:identities
6131:complement
6064:hereditary
6047:Set theory
4833:References
4703:generative
3595:LR parsers
3591:LL parsers
1291:, that is
311:parse tree
291:recognizer
119:Production
7344:Supertask
7247:Recursion
7205:decidable
7039:saturated
7017:of models
6940:deductive
6935:axiomatic
6855:Hilbert's
6842:Euclidean
6823:canonical
6746:axiomatic
6678:Signature
6607:Predicate
6496:Extension
6418:Ackermann
6343:Operation
6222:Universal
6212:Recursive
6187:Singleton
6182:Inhabited
6167:Countable
6157:Types of
6141:power set
6111:partition
6028:Predicate
5974:Predicate
5889:Syllogism
5879:Soundness
5852:Inference
5842:Tautology
5744:paradoxes
5500:Star-free
5454:Positive
5444:Decidable
5379:Positive
5303:Languages
4741:needs of
4699:described
4663:recursive
4624:include:
4565:ϵ
4562:→
4532:→
4502:→
4472:→
4442:→
4372:Σ
4229:≥
4217:∣
4164:≥
4158:∣
3978:→
3944:→
3875:Σ
3746:≥
3740:∣
3683:≥
3677:∣
3494:⇒
3426:⇒
3387:⇒
3341:⇒
3302:⇒
3263:⇒
3217:⇒
3177:⇒
3153:⇒
3088:⇒
3051:⇒
3014:⇒
2983:⇒
2931:⇒
2749:≥
2743:∣
2664:→
2630:→
2593:→
2556:→
2461:Σ
2329:Σ
2326:∪
2282:Σ
2159:∗
2155:Σ
2124:∗
2117:⇒
2108:∣
2103:∗
2092:∪
2089:Σ
2083:∈
2033:∗
2022:∪
2019:Σ
1985:⇒
1953:∗
1946:⇒
1898:∧
1889:∈
1883:→
1874:∧
1845:∗
1834:∪
1831:Σ
1825:∈
1801:∃
1797:⟺
1785:⇒
1756:∗
1745:∪
1742:Σ
1714:⇒
1677:Σ
1607:Σ
1560:∈
1532:ϵ
1508:Λ
1494:set union
1480:∪
1455:∗
1428:∗
1417:∪
1414:Σ
1408:→
1403:∗
1392:∪
1389:Σ
1378:∗
1367:∪
1364:Σ
1310:Σ
1235:→
1207:→
1176:→
1145:→
957:s and/or
896:→
859:→
831:→
764:repeated
702:…
615:≥
609:∣
539:⇒
521:⇒
509:⇒
445:→
411:→
392:Example 1
371:ambiguous
346:Unlike a
7329:Logicism
7322:timeline
7298:Concrete
7157:Validity
7127:T-schema
7120:Kripke's
7115:Tarski's
7110:semantic
7100:Strength
7049:submodel
7044:spectrum
7012:function
6860:Tarski's
6849:Elements
6836:geometry
6792:Robinson
6713:variable
6698:function
6671:spectrum
6661:Sentence
6617:variable
6560:Language
6513:Relation
6474:Automata
6464:Alphabet
6448:language
6302:-jection
6280:codomain
6266:Function
6227:Universe
6197:Infinite
6101:Relation
5884:Validity
5874:Argument
5772:theorem,
5298:Grammars
5145:Archived
5028:Archived
4995:Archived
4967:(1978).
4939:(1975).
4904:19519474
4806:L-system
4754:See also
4749:writers.
4747:compiler
2182:language
2175:sentence
1492:denotes
1330:disjoint
1328:that is
1293:disjoint
997:from an
717:, where
357:terminal
240:alphabet
74:Alphabet
44:a series
41:Part of
7388:Grammar
7271:Related
7068:Diagram
6966: (
6945:Hilbert
6930:Systems
6925:Theorem
6803:of the
6748:systems
6528:Formula
6523:Grammar
6439: (
6383:General
6096:Forcing
6081:Element
6001:Monadic
5776:paradox
5717:Theorem
5653:General
5521:Decider
5495:Regular
5462:Indexed
5420:Regular
5387:Indexed
4796:Grammar
2378:Example
1468:is the
1128:regular
359:symbols
299:Parsing
7398:Syntax
7034:finite
6797:Skolem
6750:
6725:Theory
6693:Symbol
6683:String
6666:atomic
6543:ground
6538:closed
6533:atomic
6489:ground
6452:syntax
6348:binary
6275:domain
6192:Finite
5957:finite
5815:Logics
5774:
5722:Theory
5573:Finite
5505:Finite
5350:Type-3
5341:Type-2
5323:Type-1
5317:Type-0
5079:et al.
4975:
4947:
4923:Mouton
4902:
4856:
4811:Lojban
4035:time (
2912:are:
2769:where
2411:where
1446:where
496:aababb
248:syntax
79:Syntax
7024:Model
6772:Peano
6629:Proof
6469:Arity
6398:Naive
6285:image
6217:Fuzzy
6177:Empty
6126:union
6071:Class
5712:Model
5702:Lemma
5660:Axiom
5531:PTIME
5153:JPR02
4900:S2CID
4316:with
3833:with
3545:When
1638:or a
1589:tuple
1332:from
490:with
484:aaSbb
478:with
242:of a
7147:Type
6950:list
6754:list
6731:list
6720:Term
6654:rank
6548:open
6442:list
6254:Maps
6159:sets
6018:Free
5988:list
5738:list
5665:list
5278:and
4973:ISBN
4945:ISBN
4854:ISBN
4745:and
4641:and
3593:and
3571:and
3539:and
2880:'s.
2180:the
380:and
355:and
6834:of
6816:of
6764:of
6296:Sur
6270:Map
6077:Ur-
6059:Set
5115:,"
5085:,"
5081:, "
5061:doi
5034:,"
4892:doi
4669:is
4114:In
4037:see
3967:2.
3933:1.
2650:4.
2616:3.
2582:2.
2545:1.
2184:of
1975:of
1524:or
1343:of
1322:of
1285:of
1224:4.
1196:3.
1165:2.
1134:1.
1103:or
934:s.
879:3.
848:2.
820:1.
744:is
480:aSb
472:aSb
434:2.
400:1.
321:).
317:in
303:set
286:set
7379::
7220:NP
6844::
6838::
6768::
6445:),
6300:Bi
6292:In
5274::
5168:.
5055:.
4898:.
4886:.
4872:^
4406:,
4364:,
3909:,
3867:,
3616:.
3605:A
2501:,
2453:,
2004:a
1520:,
569:.
492:ba
388:.
373:.
365:.
277:,
273:,
269:,
234:A
47:on
7300:/
7215:P
6970:)
6756:)
6752:(
6649:∀
6644:!
6639:∃
6600:=
6595:↔
6590:→
6585:∧
6580:∨
6575:¬
6298:/
6294:/
6268:/
6079:)
6075:(
5962:∞
5952:3
5740:)
5638:e
5631:t
5624:v
5466:—
5424:—
5391:—
5356:—
5353:—
5347:—
5344:—
5338:—
5335:—
5332:—
5329:—
5326:—
5320:—
5264:e
5257:t
5250:v
5067:.
5063::
5057:8
4981:.
4953:.
4925:.
4906:.
4894::
4888:2
4867:.
4721:.
4679:A
4675:A
4658:.
4599:)
4596:n
4593:(
4590:O
4559:B
4538:B
4535:b
4529:B
4508:B
4505:b
4499:A
4478:A
4475:a
4469:A
4448:A
4445:a
4439:S
4414:S
4393:}
4389:b
4386:,
4383:a
4379:{
4375:=
4351:}
4347:B
4344:,
4341:A
4338:,
4335:S
4331:{
4327:=
4324:N
4302:3
4298:G
4277:b
4257:a
4236:}
4232:1
4226:n
4223:,
4220:m
4212:m
4208:b
4202:n
4198:a
4193:{
4171:}
4167:1
4161:n
4153:n
4149:b
4143:n
4139:a
4134:{
4090:n
4070:)
4065:3
4061:n
4057:(
4054:O
4023:)
4018:3
4014:n
4010:(
4007:O
3984:b
3981:a
3975:S
3953:b
3950:S
3947:a
3941:S
3917:S
3896:}
3892:b
3889:,
3886:a
3882:{
3878:=
3854:}
3851:S
3848:{
3844:=
3841:N
3819:2
3815:G
3794:b
3774:a
3753:}
3749:1
3743:n
3735:n
3731:b
3725:n
3721:a
3716:{
3690:}
3686:1
3680:n
3672:n
3668:c
3662:n
3658:b
3652:n
3648:a
3643:{
3639:=
3636:)
3633:G
3630:(
3627:L
3524:i
3520:Q
3516:P
3502:Q
3497:i
3489:P
3460:c
3457:c
3454:c
3451:b
3447:b
3444:b
3440:a
3437:a
3434:a
3429:4
3421:c
3418:c
3415:c
3411:b
3408:b
3404:B
3401:a
3398:a
3395:a
3390:4
3375:c
3372:c
3369:c
3366:b
3363:B
3359:B
3356:a
3352:a
3349:a
3344:3
3336:c
3333:c
3330:c
3327:b
3323:B
3320:a
3316:B
3313:a
3310:a
3305:3
3297:c
3294:c
3291:c
3288:b
3285:a
3282:B
3278:B
3275:a
3271:a
3266:3
3251:c
3248:c
3244:c
3241:b
3238:a
3234:B
3231:a
3228:B
3225:a
3220:2
3205:c
3201:c
3198:S
3195:B
3192:a
3188:B
3185:a
3180:1
3171:c
3168:S
3165:B
3162:a
3156:1
3143:S
3113:c
3110:c
3106:b
3103:b
3099:a
3096:a
3091:4
3076:c
3073:c
3070:b
3066:B
3063:a
3059:a
3054:3
3039:c
3035:c
3032:b
3029:a
3025:B
3022:a
3017:2
3001:c
2998:S
2995:B
2992:a
2986:1
2973:S
2946:c
2943:b
2940:a
2934:2
2925:S
2900:)
2897:G
2894:(
2891:L
2868:c
2848:b
2828:a
2808:a
2798:n
2782:n
2778:a
2756:}
2752:1
2746:n
2738:n
2734:c
2728:n
2724:b
2718:n
2714:a
2709:{
2705:=
2702:)
2699:G
2696:(
2693:L
2670:b
2667:b
2661:b
2658:B
2636:B
2633:a
2627:a
2624:B
2602:c
2599:b
2596:a
2590:S
2568:c
2565:S
2562:B
2559:a
2553:S
2529:P
2509:S
2488:}
2484:c
2481:,
2478:b
2475:,
2472:a
2468:{
2464:=
2440:}
2436:B
2433:,
2430:S
2426:{
2422:=
2419:N
2399:G
2387:.
2362:S
2338:)
2335:P
2332:,
2323:N
2320:(
2297:)
2294:S
2291:,
2288:P
2285:,
2279:,
2276:N
2273:(
2270:=
2267:G
2255:.
2243:G
2223:)
2220:G
2217:(
2213:L
2192:G
2177:.
2133:}
2129:w
2120:G
2111:S
2099:)
2095:N
2086:(
2080:w
2076:{
2055:S
2029:)
2025:N
2016:(
1988:G
1949:G
1919:)
1916:v
1913:q
1910:u
1907:=
1904:y
1901:(
1895:)
1892:P
1886:q
1880:p
1877:(
1871:)
1868:v
1865:p
1862:u
1859:=
1856:x
1853:(
1850::
1841:)
1837:N
1828:(
1822:q
1819:,
1816:p
1813:,
1810:v
1807:,
1804:u
1793:y
1788:G
1780:x
1752:)
1748:N
1739:(
1717:G
1692:)
1689:S
1686:,
1683:P
1680:,
1674:,
1671:N
1668:(
1665:=
1662:G
1622:)
1619:S
1616:,
1613:P
1610:,
1604:,
1601:N
1598:(
1583:.
1563:N
1557:S
1522:e
1424:)
1420:N
1411:(
1399:)
1395:N
1386:(
1383:N
1374:)
1370:N
1361:(
1341:P
1336:.
1334:N
1299:.
1297:G
1283:N
1275:G
1238:b
1232:S
1210:a
1204:S
1182:S
1179:b
1173:S
1151:S
1148:a
1142:S
1111:b
1091:a
1071:S
1051:b
1031:S
1028:S
1025:S
1005:S
985:b
965:b
945:a
922:S
899:b
893:a
890:S
887:a
865:S
862:S
856:S
834:a
828:S
792:n
772:k
752:a
730:k
726:a
705:}
699:,
696:b
693:b
690:b
687:a
684:b
681:a
678:a
675:a
672:,
669:b
666:b
663:a
660:b
657:a
654:a
651:,
648:b
645:a
642:b
639:a
636:,
633:a
630:b
627:{
624:=
621:}
618:0
612:n
604:n
600:b
596:a
593:b
588:n
584:a
580:{
557:b
554:b
551:a
548:b
545:a
542:a
536:b
533:b
530:S
527:a
524:a
518:b
515:S
512:a
506:S
488:S
476:S
468:S
451:a
448:b
442:S
420:b
417:S
414:a
408:S
386:S
382:b
378:a
289:"
223:e
216:t
209:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
