6447:
509:
3455:
47:
342:
744:
While formal language theory usually concerns itself with formal languages that are described by some syntactic rules, the actual definition of the concept "formal language" is only as above: a (possibly infinite) set of finite-length strings composed from a given alphabet, no more and no less. In
936:
Formal languages are used as tools in multiple disciplines. However, formal language theory rarely concerns itself with particular languages (except as examples), but is mainly concerned with the study of various types of formalisms to describe languages. For instance, a language can be given as
871:
However, even over a finite (non-empty) alphabet such as Σ = {a, b} there are an infinite number of finite-length words that can potentially be expressed: "a", "abb", "ababba", "aaababbbbaab", .... Therefore, formal languages are typically infinite, and describing an infinite
2981:
757:
may be closer to the intuitive concept of a "language", one described by syntactic rules. By an abuse of the definition, a particular formal language is often thought of as being accompanied with a formal grammar that describes it.
2562:
1020:
Surprisingly often, the answer to these decision problems is "it cannot be done at all", or "it is extremely expensive" (with a characterization of how expensive). Therefore, formal language theory is a major application area of
2433:
1057:
Certain operations on languages are common. This includes the standard set operations, such as union, intersection, and complement. Another class of operation is the element-wise application of string operations.
2857:
2221:
2102:
1832:
of classes of languages. A class of languages is closed under a particular operation when the operation, applied to languages in the class, always produces a language in the same class again. For instance, the
601:. He published "Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas" ("On a system of notations and symbols intended to facilitate the description of machines").
3131:
733:
of Σ, that is, a set of words over that alphabet. Sometimes the sets of words are grouped into expressions, whereas rules and constraints may be formulated for the creation of 'well-formed expressions'.
3416:
Of course, compilers do more than just parse the source code – they usually translate it into some executable format. Because of this, a parser usually outputs more than a yes/no answer, typically an
3529:
one expression from one or more other expressions. Although a formal language can be identified with its formulas, a formal system cannot be likewise identified by its theorems. Two formal systems
3327:
2311:
1730:
4078:
659:
number of elements; however, most definitions in formal language theory specify alphabets with a finite number of elements, and many results apply only to them. It often makes sense to use an
2806:
2684:
1677:
1631:
1582:
3216:
1811:
698:
one can combine two words to form a new word, whose length is the sum of the lengths of the original words. The result of concatenating a word with the empty word is the original word.
4351:
3588:
may have all the same theorems and yet differ in some significant proof-theoretic way (a formula A may be a syntactic consequence of a formula B in one but not another for instance).
3586:
3413:, attempts to decide if the source program is syntactically valid, that is if it is well formed with respect to the programming language grammar for which the compiler was built.
492:
aspects of such languages—that is, their internal structural patterns. Formal language theory sprang out of linguistics, as a way of understanding the syntactic regularities of
1182:
4826:
3554:
1345:
1435:
4322:
5501:
2851:
1502:
1482:
1133:
3036:
1961:
1934:
1907:
1880:
1529:
1462:
1399:
1372:
1299:
1252:
1113:
1086:
1205:
3264:
2729:
2607:
1753:
1272:
1225:
3607:. The last sentence in the sequence is a theorem of a formal system. Formal proofs are useful because their theorems can be interpreted as true propositions.
2465:
5584:
4725:
4671:
3948:
4344:
326:
586:. Post would later use this paper as the basis for a 1947 proof "that the word problem for semigroups was recursively insoluble", and later devised the
445:
and formalized versions of subsets of natural languages, in which the words of the language represent concepts that are associated with meanings or
3660:, and fixed compositional interpretation rules determine how the truth value of the formula can be derived from the interpretation of its terms; a
3395:, numeric and string literals, punctuation and operator symbols, which are themselves specified by a simpler formal language, usually by means of
5898:
4558:
4337:
2976:{\displaystyle \varphi (L_{1})=\bigcup _{\sigma _{1}\cdots \sigma _{n}\in L_{1}}\varphi (\sigma _{1})\cdot \ldots \cdot \varphi (\sigma _{n})}
834:). For instance, nowhere in these rules is there any indication that "0" means the number zero, "+" means addition, "23+4=555" is false, etc.
571:(1879) and more fully developed in his 2-volume Grundgesetze der Arithmetik (1893/1903). This described a "formal language of pure language."
6476:
6056:
4177:
3864:
478:
350:
4844:
2345:
5911:
5234:
4483:
2136:
2017:
4573:
35:
5496:
5916:
5906:
5643:
4849:
4498:
3960:
5394:
4840:
6052:
4249:
4217:
4202:
4136:
4118:
4087:
3788:
130:
4161:
3042:
623:
developed the Backus-Naur form to describe the syntax of a high level programming language, following his work in the creation of
6149:
5893:
4718:
4666:
4651:
64:
5454:
5147:
4888:
997:
What is their recognizability? (How difficult is it to decide whether a given word belongs to a language described by formalism
6481:
4527:
2003:
1026:
450:
4286:
3721:
is often expressed using an alphabet that, besides symbols such as ∧, ¬, ∀ and parentheses, contains infinitely many elements
690:). The length of a word is the number of letters it is composed of. For any alphabet, there is only one word of length 0, the
111:
6410:
6112:
5875:
5870:
5695:
5116:
4800:
3657:
3392:
3368:
68:
4262:
83:
3887:
6405:
6188:
6105:
5818:
5749:
5626:
4868:
4242:
3491:
3270:
2255:
223:
5476:
1682:
6330:
6156:
5842:
5075:
4544:
4469:
1846:
481:
is the philosophy that all of mathematics can be reduced to the syntactic manipulation of formal languages in this way.
193:
5481:
904:
the set of syntactically correct programs in a given programming language (the syntax of which is usually defined by a
842:
For finite languages, one can explicitly enumerate all well-formed words. For example, we can describe a language
90:
30:
This article is about a technical term in mathematics and computer science. For any formal type of language usage, see
5813:
5552:
4810:
4711:
4641:
4237:
3445:
2735:
2613:
544:
390:
278:
273:
178:
6208:
6203:
4281:"Preface" in Vol.1, pp. v–viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp. 1–39
1636:
1590:
405:
319:
6137:
5727:
5121:
5089:
4780:
4537:
4272:
Drafts of some chapters in the "Handbook of Formal
Language Theory", Vol. 1–3, G. Rozenberg and A. Salomaa (eds.),
4110:
1993:
1554:
470:
4854:
57:
6471:
6427:
6376:
6273:
5771:
5732:
5209:
4462:
3698:
3467:
2129:
683:
409:
312:
298:
283:
147:
97:
6268:
4883:
3163:
1758:
6198:
5737:
5589:
5572:
5295:
4775:
4614:
4609:
3649:
3616:
851:
826:, well-formed additions, and well-formed addition equalities, but it expresses only what they look like (their
1538:: the language consisting of all words that are concatenations of zero or more words in the original language;
1004:
What is their comparability? (How difficult is it to decide whether two languages, one described in formalism
578:
published four papers relating to words and language between 1906 and 1914. The last of these introduced what
4695:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
6100:
6077:
6038:
5924:
5865:
5511:
5431:
5275:
5219:
4832:
2248:
1842:
594:
79:
6390:
6117:
6095:
6062:
5955:
5801:
5786:
5759:
5710:
5594:
5529:
5354:
5320:
5315:
5189:
5020:
4997:
4625:
4563:
4488:
3673:
3638:
3620:
964:
574:
In the first half of the 20th century, several developments were made with relevance to formal languages.
258:
1033:
based on the expressive power of their generative grammar as well as the complexity of their recognizing
6320:
6173:
5965:
5683:
5419:
5325:
5184:
5169:
5050:
5025:
4568:
4516:
4329:
3693:
1983:
1834:
1829:
750:
587:
268:
6446:
632:
441:
In computer science, formal languages are used, among others, as the basis for defining the grammar of
3935:
Sobre un sistema de notaciones y símbolos destinados a facilitar la descripción de las máquinas, (pdf)
3559:
1147:
6293:
6255:
6132:
5936:
5776:
5700:
5678:
5506:
5464:
5363:
5330:
5194:
4982:
4893:
4661:
4636:
4493:
4454:
4232:
3776:
3532:
3417:
3382:
1310:
1038:
1022:
905:
606:
552:
442:
431:
3934:
6422:
6313:
6298:
6278:
6235:
6122:
6072:
5998:
5943:
5880:
5673:
5668:
5616:
5384:
5373:
5045:
4945:
4873:
4864:
4860:
4795:
4790:
4153:
4142:
3518:
3510:
3471:
3396:
1818:
583:
418:
293:
208:
6451:
6220:
6183:
6168:
6161:
6144:
5930:
5796:
5722:
5705:
5658:
5471:
5380:
5214:
5199:
5159:
5111:
5096:
5084:
5040:
5015:
4785:
4734:
4646:
4588:
4532:
4186:
3483:
2010:
1998:
971:
949:
664:
597:
introduced a formal language for the description of mechanical drawings (mechanical devices), in
218:
188:
5948:
5404:
1410:
927:
the set {the, set, of, maximal, strings, alphanumeric, ASCII, characters, on, this, line, i, e}.
345:
Structure of the syntactically well-formed, although thoroughly nonsensical, English sentence,
6386:
6193:
6003:
5993:
5885:
5766:
5601:
5577:
5358:
5342:
5247:
5224:
5101:
5070:
5035:
4930:
4765:
4381:
4213:
4198:
4173:
4132:
4114:
4083:
4007:
3956:
3860:
3852:
3784:
3718:
3688:
3604:
3429:
3372:
2836:
1825:
1030:
774:
Every nonempty string that does not contain "+" or "=" and does not start with "0" is in
648:
616:
540:
228:
31:
1487:
1467:
1118:
104:
6400:
6395:
6288:
6245:
6067:
6028:
6023:
6008:
5834:
5791:
5688:
5486:
5436:
5010:
4972:
4630:
4583:
4550:
4396:
4298:
4280:
4165:
4124:
4025:
3997:
3989:
3404:
3378:
3244:
3011:
1988:
1973:
1838:
746:
738:
493:
474:
458:
454:
370:
157:
1939:
1912:
1885:
1858:
1507:
1440:
1377:
1350:
1277:
1230:
1091:
1064:
6381:
6371:
6325:
6308:
6263:
6225:
6127:
6047:
5854:
5781:
5754:
5742:
5562:
5491:
5459:
5260:
5062:
5005:
4955:
4920:
4878:
4593:
4508:
4475:
4360:
4273:
4266:
3912:
3433:
1042:
1034:
956:
567:
427:
394:
386:
288:
263:
213:
686:) of letters. The set of all words over an alphabet Σ is usually denoted by Σ (using the
3780:
3603:) each of which is an axiom or follows from the preceding formulas in the sequence by a
3599:
is a finite sequence of well-formed formulas (which may be interpreted as sentences, or
2557:{\displaystyle L_{1}^{*}=\{\varepsilon \}\cup \{wz\mid w\in L_{1}\land z\in L_{1}^{*}\}}
1187:
6366:
6345:
6303:
6283:
6178:
6033:
5631:
5621:
5611:
5606:
5540:
5414:
5290:
5179:
5174:
5152:
4753:
4604:
4386:
4368:
4073:
4002:
3977:
3656:. In model theory, the terms that occur in a formula are interpreted as objects within
3459:
3249:
2714:
2592:
1738:
1257:
1210:
960:
942:
912:
823:
754:
556:
435:
423:
398:
253:
233:
203:
198:
183:
4253:
508:
6465:
6340:
6018:
5525:
5310:
5300:
5270:
5255:
4925:
4689:
4069:
3807:
3678:
3463:
3449:
2338:
1141:
695:
656:
602:
562:
412:
called words. Words that belong to a particular formal language are sometimes called
173:
4310:
1849:
studies the most common closure properties of language families in their own right.
792:
if and only if there is exactly one "=", and it separates two valid strings of
717:; this breaks the letter/word metaphor and replaces it by a word/sentence metaphor.
565:
attempted to realize
Leibniz's ideas, through a notational system first outlined in
6240:
6087:
5988:
5980:
5860:
5808:
5717:
5653:
5636:
5567:
5426:
5285:
4987:
4770:
4190:
3653:
3624:
3526:
3425:
919:
612:
3637:, the set of possible formulas of a particular logic is a formal language, and an
4259:
3770:
3633:
that give meaning to the elements of the language. For instance, in mathematical
615:
devised an abstract representation of formal and natural languages, known as the
6350:
6230:
5409:
5399:
5346:
5030:
4950:
4935:
4815:
4760:
4656:
4578:
4503:
4316:
3880:
3683:
3664:
for a formula is an interpretation of terms such that the formula becomes true.
3642:
3600:
1535:
687:
620:
548:
374:
366:
46:
4304:
3454:
17:
5280:
5135:
5106:
4912:
4169:
3421:
3420:. This is used by subsequent stages of the compiler to eventually generate an
3388:
628:
6432:
6335:
5388:
5305:
5265:
5229:
5165:
4977:
4967:
4940:
3829:
3630:
1963:
are in the language family given by the column). After
Hopcroft and Ullman.
975:
831:
579:
575:
489:
446:
4011:
3993:
803:
if and only if every "+" in the string separates two valid strings of
745:
practice, there are many languages that can be described by rules, such as
4292:
978:
that asks a sequence of related YES/NO questions) produces the answer YES.
876: = {a, b, ab, cba}. Here are some examples of formal languages:
6417:
6215:
5663:
5368:
4962:
1837:
are known to be closed under union, concatenation, and intersection with
660:
341:
6013:
4805:
3475:
1046:
672:
624:
462:
354:
2428:{\displaystyle L_{1}\cdot L_{2}=\{wz\mid w\in L_{1}\land z\in L_{2}\}}
770:
over the alphabet Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:
4703:
3400:
827:
730:
598:
4293:"Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1
3629:
Formal languages are entirely syntactic in nature, but may be given
3521:, which may be interpreted as valid rules of inference, or a set of
2216:{\displaystyle L_{1}\cap L_{2}=\{w\mid w\in L_{1}\land w\in L_{2}\}}
864:
737:
In computer science and mathematics, which do not usually deal with
2097:{\displaystyle L_{1}\cup L_{2}=\{w\mid w\in L_{1}\lor w\in L_{2}\}}
901:
times (this is the set of words consisting only of the symbol "a");
404:
The alphabet of a formal language consists of symbols, letters, or
5557:
4903:
4748:
4619:
3634:
3522:
3453:
3387:, identifies the tokens of the programming language grammar, e.g.
922:
702:
668:
466:
362:
340:
1841:, but not closed under intersection or complement. The theory of
822:, but the string "=234=+" is not. This formal language expresses
631:
was the secretary/editor for the ALGOL60 Report in which he used
3409:
1978:
382:
4707:
4333:
4129:
Algebraic and automata theoretic properties of formal languages
3808:"In the prehistory of formal language theory: Gauss Languages"
503:
40:
4323:"Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215–267
663:
in the usual sense of the word, or more generally any finite
582:
later termed 'Thue
Systems', and gave an early example of an
4688:
Each category of languages, except those marked by a , is a
3569:
3565:
3541:
3538:
3126:{\displaystyle h^{-1}(L_{1})=\bigcup _{w\in L_{1}}h^{-1}(w)}
1401:
consists of all strings that are contained in both languages
461:
are defined as the sets of the formal languages that can be
4079:
Introduction to
Automata Theory, Languages, and Computation
3648:
The study of interpretations of formal languages is called
1045:
provide a good compromise between expressivity and ease of
897:
ranges over the natural numbers and "a" means "a" repeated
4049:, Chapter 11: Closure properties of families of languages.
4311:"Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679–746
3978:"Formal language theory: refining the Chomsky hierarchy"
3937:, pp. 25–30, Revista de Obras Públicas, 17 January 1907.
3652:. In mathematical logic, this is often done in terms of
741:, the adjective "formal" is often omitted as redundant.
982:
Typical questions asked about such formalisms include:
520:
473:, formal languages are used to represent the syntax of
3853:"Influences of Mathematical Logic on Computer Science"
4317:"Automata for matching patterns", Chapter 9 in Vol. 2
4082:. Reading, Massachusetts: Addison-Wesley Publishing.
3641:
assigns a meaning to each of the formulas—usually, a
3562:
3535:
3273:
3252:
3166:
3045:
3014:
2860:
2839:
2738:
2717:
2616:
2595:
2468:
2348:
2258:
2139:
2020:
1942:
1915:
1888:
1861:
1761:
1741:
1685:
1639:
1593:
1557:
1510:
1490:
1470:
1443:
1413:
1380:
1353:
1313:
1280:
1260:
1233:
1213:
1190:
1150:
1121:
1094:
1067:
3322:{\displaystyle L\cap R=\{w\mid w\in L\land w\in R\}}
2306:{\displaystyle \neg L_{1}=\{w\mid w\not \in L_{1}\}}
818:
Under these rules, the string "23+4=555" is in
766:
The following rules describe a formal language
6359:
6254:
6086:
5979:
5831:
5524:
5447:
5341:
5245:
5134:
5061:
4996:
4911:
4902:
4824:
4741:
3857:
The universal Turing machine: a half-century survey
3517:). The deductive apparatus may consist of a set of
1725:{\displaystyle w^{R}=\sigma _{n}\cdots \sigma _{1}}
948:those strings described or matched by a particular
682:over an alphabet can be any finite sequence (i.e.,
422:. A formal language is often defined by means of a
71:. Unsourced material may be challenged and removed.
3775:. Texts in Computer Science. Springer. p. 8.
3580:
3548:
3474:. The set of well-formed formulas is divided into
3377:A compiler usually has two distinct components. A
3321:
3258:
3210:
3125:
3030:
2975:
2845:
2800:
2723:
2678:
2601:
2556:
2427:
2305:
2215:
2096:
1955:
1928:
1901:
1874:
1805:
1747:
1724:
1671:
1625:
1576:
1523:
1496:
1476:
1456:
1429:
1393:
1366:
1339:
1293:
1266:
1246:
1219:
1199:
1176:
1127:
1107:
1080:
694:, which is often denoted by e, ε, λ or even Λ. By
4291:Jean-Michel Autebert, Jean Berstel, Luc Boasson,
3982:Philosophical Transactions of the Royal Society B
1049:, and are widely used in practical applications.
647:, in the context of formal languages, can be any
547:, a universal and formal language which utilised
3509:) consists of a formal language together with a
2801:{\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}
2679:{\displaystyle h(L_{1})=\{h(w)\mid w\in L_{1}\}}
1672:{\displaystyle \sigma _{1},\ldots ,\sigma _{n}}
1626:{\displaystyle w=\sigma _{1}\cdots \sigma _{n}}
994:can describe? Can it describe other languages?)
986:What is their expressive power? (Can formalism
814:other than those implied by the previous rules.
799:A string containing "+" but not "=" is in
457:are typically defined as formal languages, and
4046:
3976:Jager, Gerhard; Rogers, James (19 July 2012).
397:according to a specific set of rules called a
4719:
4345:
4305:"Morphisms", Chapter 7 in Vol. 1, pp. 439–510
4299:"Combinatorics of Words", Chapter 6 in Vol. 1
4260:"Notes on Formal Language Theory and Parsing"
3949:"The Global Evolution of Computer Technology"
1577:{\displaystyle \varepsilon ^{R}=\varepsilon }
320:
8:
4158:A Concise Introduction to Mathematical Logic
3428:that runs directly on the hardware, or some
3316:
3286:
3205:
3180:
2795:
2761:
2673:
2639:
2551:
2499:
2493:
2487:
2422:
2375:
2300:
2275:
2210:
2166:
2091:
2047:
1800:
1775:
1029:. Formal languages may be classified in the
872:formal language is not as simple as writing
609:for the numerical control of machine tools.
4667:Counter-free (with aperiodic finite monoid)
3525:, or have both. A formal system is used to
34:. For studies about natural languages, see
5545:
5140:
4908:
4726:
4712:
4704:
4377:
4352:
4338:
4330:
4195:Handbook of Formal Languages: Volume I-III
3953:Milestones in Analog and Digital Computing
3211:{\displaystyle L^{R}=\{w^{R}\mid w\in L\}}
1806:{\displaystyle L^{R}=\{w^{R}\mid w\in L\}}
327:
313:
142:
27:Sequence of words formed by specific rules
4297:Christian Choffrut and Juhani Karhumäki,
4001:
3742:, … that play the role of variables.
3564:
3563:
3561:
3537:
3536:
3534:
3470:may be broadly divided into nonsense and
3272:
3251:
3187:
3171:
3165:
3105:
3093:
3082:
3066:
3050:
3044:
3019:
3013:
2964:
2936:
2918:
2905:
2892:
2887:
2871:
2859:
2838:
2789:
2749:
2737:
2716:
2667:
2627:
2615:
2594:
2545:
2540:
2521:
2478:
2473:
2467:
2416:
2397:
2366:
2353:
2347:
2294:
2266:
2257:
2204:
2185:
2157:
2144:
2138:
2085:
2066:
2038:
2025:
2019:
1947:
1941:
1920:
1914:
1893:
1887:
1866:
1860:
1855:Closure properties of language families (
1782:
1766:
1760:
1740:
1716:
1703:
1690:
1684:
1663:
1644:
1638:
1617:
1604:
1592:
1562:
1556:
1515:
1509:
1489:
1469:
1448:
1442:
1421:
1412:
1385:
1379:
1358:
1352:
1331:
1318:
1312:
1285:
1279:
1259:
1238:
1232:
1212:
1189:
1168:
1155:
1149:
1120:
1099:
1093:
1072:
1066:
131:Learn how and when to remove this message
4287:"Regular Languages", Chapter 2 in Vol. 1
3399:. At the most basic conceptual level, a
1853:
1115:are languages over some common alphabet
1016:again, are actually the same language?).
635:to describe the Formal part of ALGOL60.
3760:
3710:
990:describe every language that formalism
911:the set of inputs upon which a certain
347:"Colorless green ideas sleep furiously"
156:
4559:Linear context-free rewriting language
4147:Introduction to Formal Language Theory
590:for the creation of formal languages.
4484:Linear context-free rewriting systems
4279:Alexandru Mateescu and Arto Salomaa,
3381:, sometimes generated by a tool like
465:with limited computational power. In
7:
3440:Formal theories, systems, and proofs
1679:are elements of some alphabet), let
1184:consists of all strings of the form
705:, the alphabet is also known as the
701:In some applications, especially in
69:adding citations to reliable sources
4321:Dora Giammarresi, Antonio Restivo,
788:A string containing "=" is in
36:Formal semantics (natural language)
4692:of the category directly above it.
3893:from the original on 30 April 2021
3881:"Thue's 1914 paper: a translation"
2259:
1491:
1471:
1414:
1122:
858:, which contains no words at all (
850: = {a, b, ab, cba}. The
25:
4303:Tero Harju and Juhani Karhumäki,
3769:Reghizzi, Stefano Crespi (2009).
932:Language-specification formalisms
854:case of this construction is the
194:Semantics (programming languages)
6445:
3772:Formal Languages and Compilation
3581:{\displaystyle {\mathcal {FS'}}}
3494:expressed in a formal language.
1177:{\displaystyle L_{1}\cdot L_{2}}
941:those strings generated by some
507:
45:
4162:Springer Science+Business Media
3549:{\displaystyle {\mathcal {FS}}}
1340:{\displaystyle L_{1}\cap L_{2}}
955:those strings accepted by some
605:rated it as an equivalent to a
451:computational complexity theory
56:needs additional citations for
4315:M. Crochemore and C. Hancart,
3369:Syntax (programming languages)
3120:
3114:
3072:
3059:
2970:
2957:
2942:
2929:
2877:
2864:
2773:
2767:
2755:
2742:
2651:
2645:
2633:
2620:
1854:
1847:abstract families of languages
925:characters on this line, i.e.,
918:the set of maximal strings of
1:
6406:History of mathematical logic
2711:ε-free (string) homomorphism
1484:consists of all strings over
970:those strings for which some
655:. An alphabet may contain an
488:studies primarily the purely
6477:Theoretical computer science
6331:Primitive recursive function
4047:Hopcroft & Ullman (1979)
555:investigated the problem of
4254:Formal Language Definitions
4238:Encyclopedia of Mathematics
3795:An alphabet is a finite set
3446:Theory (mathematical logic)
3403:, sometimes generated by a
1735:then for a formal language
545:characteristica universalis
543:imagined and described the
279:Programming language theory
274:Natural language processing
6498:
5395:Schröder–Bernstein theorem
5122:Monadic predicate calculus
4781:Foundations of mathematics
4574:Deterministic context-free
4499:Deterministic context-free
4160:(3rd ed.). New York:
4111:Cambridge University Press
3955:. Springer. p. 1212.
3947:Bruderer, Herbert (2021).
3933:Torres Quevedo, Leonardo.
3614:
3611:Interpretations and models
3443:
3366:
1430:{\displaystyle \neg L_{1}}
781:The string "0" is in
651:; its elements are called
471:foundations of mathematics
29:
6441:
6428:Philosophy of mathematics
6377:Automated theorem proving
5548:
5502:Von Neumann–Bernays–Gödel
5143:
4685:
4647:Nondeterministic pushdown
4375:
4212:, D. Van Nostrand, 1957,
4170:10.1007/978-1-4419-1221-3
3859:. Springer. p. 290.
3699:String (computer science)
299:Automated theorem proving
284:Computational linguistics
4265:21 November 2007 at the
4107:Logic for Mathematicians
3855:. In Rolf Herken (ed.).
3617:Formal semantics (logic)
2846:{\displaystyle \varphi }
1828:are used to investigate
1587:for each non-empty word
1551:be the empty word, then
729:over an alphabet Σ is a
434:, which consists of its
6078:Self-verifying theories
5899:Tarski's axiomatization
4850:Tarski's undefinability
4845:incompleteness theorems
4149:, Addison-Wesley, 1978.
4131:, North-Holland, 1975,
3658:mathematical structures
3458:This diagram shows the
1497:{\displaystyle \Sigma }
1477:{\displaystyle \Sigma }
1128:{\displaystyle \Sigma }
1053:Operations on languages
830:), not what they mean (
709:and words are known as
595:Leonardo Torres Quevedo
6482:Combinatorics on words
6452:Mathematics portal
6063:Proof of impossibility
5711:propositional variable
5021:Propositional calculus
4652:Deterministic pushdown
4528:Recursively enumerable
4250:University of Maryland
3994:10.1098/rstb.2012.0077
3674:Combinatorics on words
3621:Interpretation (logic)
3582:
3550:
3479:
3323:
3260:
3212:
3127:
3032:
3031:{\displaystyle h^{-1}}
2977:
2847:
2802:
2725:
2680:
2603:
2589:(String) homomorphism
2558:
2429:
2307:
2217:
2098:
1957:
1930:
1903:
1876:
1835:context-free languages
1807:
1749:
1726:
1673:
1627:
1578:
1525:
1498:
1478:
1458:
1431:
1395:
1368:
1341:
1295:
1268:
1248:
1221:
1201:
1178:
1129:
1109:
1082:
965:finite-state automaton
751:context-free languages
639:Words over an alphabet
486:formal language theory
479:mathematical formalism
408:that concatenate into
358:
259:Propositional calculus
6321:Kolmogorov complexity
6274:Computably enumerable
6174:Model complete theory
5966:Principia Mathematica
5026:Propositional formula
4855:Banach–Tarski paradox
4210:Introduction to Logic
3851:Martin Davis (1995).
3694:Mathematical notation
3583:
3551:
3457:
3363:Programming languages
3324:
3261:
3213:
3128:
3033:
3008:Inverse homomorphism
2978:
2848:
2803:
2726:
2681:
2604:
2559:
2430:
2308:
2218:
2099:
1958:
1956:{\displaystyle L_{2}}
1931:
1929:{\displaystyle L_{1}}
1904:
1902:{\displaystyle L_{2}}
1877:
1875:{\displaystyle L_{1}}
1808:
1750:
1727:
1674:
1628:
1579:
1526:
1524:{\displaystyle L_{1}}
1499:
1479:
1459:
1457:{\displaystyle L_{1}}
1432:
1396:
1394:{\displaystyle L_{2}}
1369:
1367:{\displaystyle L_{1}}
1342:
1296:
1294:{\displaystyle L_{2}}
1269:
1249:
1247:{\displaystyle L_{1}}
1222:
1202:
1179:
1130:
1110:
1108:{\displaystyle L_{2}}
1083:
1081:{\displaystyle L_{1}}
1039:Context-free grammars
1008:and one in formalism
810:No string is in
539:In the 17th century,
443:programming languages
344:
269:Mathematical notation
6269:Church–Turing thesis
6256:Computability theory
5465:continuum hypothesis
4983:Square of opposition
4841:Gödel's completeness
4637:Tree stack automaton
4154:Rautenberg, Wolfgang
4026:"John Warner Backus"
3560:
3533:
3519:transformation rules
3472:well-formed formulas
3418:abstract syntax tree
3271:
3250:
3243:Intersection with a
3164:
3043:
3012:
2858:
2837:
2736:
2715:
2614:
2593:
2466:
2346:
2256:
2137:
2018:
1940:
1913:
1886:
1859:
1759:
1739:
1683:
1637:
1591:
1555:
1508:
1488:
1468:
1441:
1411:
1378:
1351:
1311:
1278:
1258:
1231:
1211:
1188:
1148:
1119:
1092:
1065:
1023:computability theory
906:context-free grammar
607:programming language
553:Carl Friedrich Gauss
432:context-free grammar
419:well-formed formulas
65:improve this article
6423:Mathematical object
6314:P versus NP problem
6279:Computable function
6073:Reverse mathematics
5999:Logical consequence
5876:primitive recursive
5871:elementary function
5644:Free/bound variable
5497:Tarski–Grothendieck
5016:Logical connectives
4946:Logical equivalence
4796:Logical consequence
4545:range concatenation
4470:range concatenation
4269:, 29 November 2002.
4143:Michael A. Harrison
3988:(1598): 1956–1970.
3781:2009flc..book.....C
3511:deductive apparatus
3462:divisions within a
3397:regular expressions
2550:
2483:
1964:
1819:String homomorphism
893:= {a} = {a}, where
584:undecidable problem
294:Formal verification
209:Well-formed formula
6221:Transfer principle
6184:Semantics of logic
6169:Categorical theory
6145:Non-standard model
5659:Logical connective
4786:Information theory
4735:Mathematical logic
4197:, Springer, 1997,
4187:Grzegorz Rozenberg
4099:General references
4074:Ullman, Jeffrey D.
3886:. 28 August 2013.
3578:
3546:
3484:mathematical logic
3480:
3468:Strings of symbols
3319:
3256:
3208:
3123:
3100:
3028:
2973:
2925:
2843:
2798:
2721:
2676:
2599:
2554:
2536:
2469:
2425:
2303:
2213:
2094:
1953:
1926:
1899:
1872:
1830:closure properties
1803:
1745:
1722:
1669:
1623:
1574:
1521:
1494:
1474:
1454:
1427:
1391:
1364:
1337:
1291:
1264:
1244:
1217:
1200:{\displaystyle vw}
1197:
1174:
1125:
1105:
1078:
1061:Examples: suppose
972:decision procedure
950:regular expression
753:. The notion of a
725:A formal language
665:character encoding
519:. You can help by
463:parsed by machines
459:complexity classes
389:are taken from an
359:
351:historical example
219:Regular expression
6459:
6458:
6391:Abstract category
6194:Theories of truth
6004:Rule of inference
5994:Natural deduction
5975:
5974:
5520:
5519:
5225:Cartesian product
5130:
5129:
5036:Many-valued logic
5011:Boolean functions
4894:Russell's paradox
4869:diagonal argument
4766:First-order logic
4701:
4700:
4680:
4679:
4642:Embedded pushdown
4538:Context-sensitive
4463:Context-sensitive
4397:Abstract machines
4382:Chomsky hierarchy
4233:"Formal language"
4179:978-1-4419-1220-6
4070:Hopcroft, John E.
3866:978-3-211-82637-9
3832:. 5 December 2019
3719:first-order logic
3689:Grammar framework
3605:rule of inference
3478:and non-theorems.
3430:intermediate code
3373:Compiler-compiler
3353:
3352:
3259:{\displaystyle R}
3078:
2883:
2724:{\displaystyle h}
2602:{\displaystyle h}
1839:regular languages
1826:string operations
1748:{\displaystyle L}
1274:is a string from
1267:{\displaystyle w}
1227:is a string from
1220:{\displaystyle v}
1031:Chomsky hierarchy
1027:complexity theory
747:regular languages
739:natural languages
617:Chomsky hierarchy
541:Gottfried Leibniz
537:
536:
494:natural languages
475:axiomatic systems
455:decision problems
414:well-formed words
337:
336:
229:Ground expression
189:Semantics (logic)
141:
140:
133:
115:
80:"Formal language"
32:Literary language
16:(Redirected from
6489:
6472:Formal languages
6450:
6449:
6401:History of logic
6396:Category of sets
6289:Decision problem
6068:Ordinal analysis
6009:Sequent calculus
5907:Boolean algebras
5847:
5846:
5821:
5792:logical/constant
5546:
5532:
5455:Zermelo–Fraenkel
5206:Set operations:
5141:
5078:
4909:
4889:Löwenheim–Skolem
4776:Formal semantics
4728:
4721:
4714:
4705:
4696:
4693:
4657:Visibly pushdown
4631:Thread automaton
4579:Visibly pushdown
4547:
4504:Visibly pushdown
4472:
4459:(no common name)
4378:
4365:formal languages
4354:
4347:
4340:
4331:
4246:
4208:Patrick Suppes,
4183:
4125:Seymour Ginsburg
4105:A. G. Hamilton,
4093:
4050:
4044:
4038:
4037:
4035:
4033:
4022:
4016:
4015:
4005:
3973:
3967:
3966:
3944:
3938:
3931:
3925:
3924:
3922:
3920:
3915:. September 2001
3913:"Emil Leon Post"
3909:
3903:
3902:
3900:
3898:
3892:
3885:
3877:
3871:
3870:
3848:
3842:
3841:
3839:
3837:
3826:
3820:
3819:
3817:
3815:
3804:
3798:
3797:
3765:
3743:
3715:
3650:formal semantics
3587:
3585:
3584:
3579:
3577:
3576:
3575:
3555:
3553:
3552:
3547:
3545:
3544:
3515:deductive system
3503:logical calculus
3432:that requires a
3412:
3405:parser generator
3385:
3379:lexical analyzer
3328:
3326:
3325:
3320:
3265:
3263:
3262:
3257:
3245:regular language
3217:
3215:
3214:
3209:
3192:
3191:
3176:
3175:
3132:
3130:
3129:
3124:
3113:
3112:
3099:
3098:
3097:
3071:
3070:
3058:
3057:
3037:
3035:
3034:
3029:
3027:
3026:
2982:
2980:
2979:
2974:
2969:
2968:
2941:
2940:
2924:
2923:
2922:
2910:
2909:
2897:
2896:
2876:
2875:
2852:
2850:
2849:
2844:
2807:
2805:
2804:
2799:
2794:
2793:
2754:
2753:
2730:
2728:
2727:
2722:
2685:
2683:
2682:
2677:
2672:
2671:
2632:
2631:
2608:
2606:
2605:
2600:
2563:
2561:
2560:
2555:
2549:
2544:
2526:
2525:
2482:
2477:
2434:
2432:
2431:
2426:
2421:
2420:
2402:
2401:
2371:
2370:
2358:
2357:
2312:
2310:
2309:
2304:
2299:
2298:
2271:
2270:
2222:
2220:
2219:
2214:
2209:
2208:
2190:
2189:
2162:
2161:
2149:
2148:
2103:
2101:
2100:
2095:
2090:
2089:
2071:
2070:
2043:
2042:
2030:
2029:
1965:
1962:
1960:
1959:
1954:
1952:
1951:
1935:
1933:
1932:
1927:
1925:
1924:
1908:
1906:
1905:
1900:
1898:
1897:
1881:
1879:
1878:
1873:
1871:
1870:
1812:
1810:
1809:
1804:
1787:
1786:
1771:
1770:
1754:
1752:
1751:
1746:
1731:
1729:
1728:
1723:
1721:
1720:
1708:
1707:
1695:
1694:
1678:
1676:
1675:
1670:
1668:
1667:
1649:
1648:
1632:
1630:
1629:
1624:
1622:
1621:
1609:
1608:
1583:
1581:
1580:
1575:
1567:
1566:
1530:
1528:
1527:
1522:
1520:
1519:
1504:that are not in
1503:
1501:
1500:
1495:
1483:
1481:
1480:
1475:
1464:with respect to
1463:
1461:
1460:
1455:
1453:
1452:
1436:
1434:
1433:
1428:
1426:
1425:
1400:
1398:
1397:
1392:
1390:
1389:
1373:
1371:
1370:
1365:
1363:
1362:
1346:
1344:
1343:
1338:
1336:
1335:
1323:
1322:
1300:
1298:
1297:
1292:
1290:
1289:
1273:
1271:
1270:
1265:
1253:
1251:
1250:
1245:
1243:
1242:
1226:
1224:
1223:
1218:
1206:
1204:
1203:
1198:
1183:
1181:
1180:
1175:
1173:
1172:
1160:
1159:
1134:
1132:
1131:
1126:
1114:
1112:
1111:
1106:
1104:
1103:
1087:
1085:
1084:
1079:
1077:
1076:
1043:regular grammars
892:
883:= Σ, the set of
882:
867:
862:
849:
845:
821:
813:
806:
802:
795:
791:
784:
777:
769:
633:Backus–Naur form
588:canonical system
532:
529:
511:
504:
371:computer science
329:
322:
315:
158:Formal languages
143:
136:
129:
125:
122:
116:
114:
73:
49:
41:
21:
6497:
6496:
6492:
6491:
6490:
6488:
6487:
6486:
6462:
6461:
6460:
6455:
6444:
6437:
6382:Category theory
6372:Algebraic logic
6355:
6326:Lambda calculus
6264:Church encoding
6250:
6226:Truth predicate
6082:
6048:Complete theory
5971:
5840:
5836:
5832:
5827:
5819:
5539: and
5535:
5530:
5516:
5492:New Foundations
5460:axiom of choice
5443:
5405:Gödel numbering
5345: and
5337:
5241:
5126:
5076:
5057:
5006:Boolean algebra
4992:
4956:Equiconsistency
4921:Classical logic
4898:
4879:Halting problem
4867: and
4843: and
4831: and
4830:
4825:Theorems (
4820:
4737:
4732:
4702:
4697:
4694:
4687:
4681:
4676:
4598:
4542:
4521:
4467:
4448:
4371:
4369:formal grammars
4361:Automata theory
4358:
4309:Jean-Eric Pin,
4274:Springer Verlag
4267:Wayback Machine
4231:
4228:
4223:
4180:
4152:
4096:
4090:
4068:
4059:
4054:
4053:
4045:
4041:
4031:
4029:
4028:. February 2016
4024:
4023:
4019:
3975:
3974:
3970:
3963:
3946:
3945:
3941:
3932:
3928:
3918:
3916:
3911:
3910:
3906:
3896:
3894:
3890:
3883:
3879:
3878:
3874:
3867:
3850:
3849:
3845:
3835:
3833:
3830:"Gottlob Frege"
3828:
3827:
3823:
3813:
3811:
3806:
3805:
3801:
3791:
3768:
3766:
3762:
3757:
3752:
3747:
3746:
3741:
3734:
3727:
3716:
3712:
3707:
3670:
3627:
3615:Main articles:
3613:
3568:
3558:
3557:
3531:
3530:
3513:(also called a
3501:(also called a
3452:
3444:Main articles:
3442:
3434:virtual machine
3408:
3383:
3375:
3367:Main articles:
3365:
3360:
3269:
3268:
3248:
3247:
3183:
3167:
3162:
3161:
3101:
3089:
3062:
3046:
3041:
3040:
3015:
3010:
3009:
2960:
2932:
2914:
2901:
2888:
2867:
2856:
2855:
2835:
2834:
2785:
2745:
2734:
2733:
2713:
2712:
2663:
2623:
2612:
2611:
2591:
2590:
2517:
2464:
2463:
2412:
2393:
2362:
2349:
2344:
2343:
2290:
2262:
2254:
2253:
2200:
2181:
2153:
2140:
2135:
2134:
2081:
2062:
2034:
2021:
2016:
2015:
1943:
1938:
1937:
1916:
1911:
1910:
1889:
1884:
1883:
1862:
1857:
1856:
1778:
1762:
1757:
1756:
1737:
1736:
1712:
1699:
1686:
1681:
1680:
1659:
1640:
1635:
1634:
1613:
1600:
1589:
1588:
1558:
1553:
1552:
1511:
1506:
1505:
1486:
1485:
1466:
1465:
1444:
1439:
1438:
1417:
1409:
1408:
1381:
1376:
1375:
1354:
1349:
1348:
1327:
1314:
1309:
1308:
1281:
1276:
1275:
1256:
1255:
1234:
1229:
1228:
1209:
1208:
1186:
1185:
1164:
1151:
1146:
1145:
1117:
1116:
1095:
1090:
1089:
1068:
1063:
1062:
1055:
934:
926:
890:
880:
860:
859:
847:
843:
840:
824:natural numbers
819:
811:
804:
800:
793:
789:
782:
775:
767:
764:
723:
641:
568:Begriffsschrift
533:
527:
524:
517:needs expansion
502:
436:formation rules
428:regular grammar
379:formal language
333:
304:
303:
289:Syntax analysis
264:Predicate logic
249:
248:
239:
238:
214:Automata theory
169:
168:
137:
126:
120:
117:
74:
72:
62:
50:
39:
28:
23:
22:
18:Symbolic system
15:
12:
11:
5:
6495:
6493:
6485:
6484:
6479:
6474:
6464:
6463:
6457:
6456:
6442:
6439:
6438:
6436:
6435:
6430:
6425:
6420:
6415:
6414:
6413:
6403:
6398:
6393:
6384:
6379:
6374:
6369:
6367:Abstract logic
6363:
6361:
6357:
6356:
6354:
6353:
6348:
6346:Turing machine
6343:
6338:
6333:
6328:
6323:
6318:
6317:
6316:
6311:
6306:
6301:
6296:
6286:
6284:Computable set
6281:
6276:
6271:
6266:
6260:
6258:
6252:
6251:
6249:
6248:
6243:
6238:
6233:
6228:
6223:
6218:
6213:
6212:
6211:
6206:
6201:
6191:
6186:
6181:
6179:Satisfiability
6176:
6171:
6166:
6165:
6164:
6154:
6153:
6152:
6142:
6141:
6140:
6135:
6130:
6125:
6120:
6110:
6109:
6108:
6103:
6096:Interpretation
6092:
6090:
6084:
6083:
6081:
6080:
6075:
6070:
6065:
6060:
6050:
6045:
6044:
6043:
6042:
6041:
6031:
6026:
6016:
6011:
6006:
6001:
5996:
5991:
5985:
5983:
5977:
5976:
5973:
5972:
5970:
5969:
5961:
5960:
5959:
5958:
5953:
5952:
5951:
5946:
5941:
5921:
5920:
5919:
5917:minimal axioms
5914:
5903:
5902:
5901:
5890:
5889:
5888:
5883:
5878:
5873:
5868:
5863:
5850:
5848:
5829:
5828:
5826:
5825:
5824:
5823:
5811:
5806:
5805:
5804:
5799:
5794:
5789:
5779:
5774:
5769:
5764:
5763:
5762:
5757:
5747:
5746:
5745:
5740:
5735:
5730:
5720:
5715:
5714:
5713:
5708:
5703:
5693:
5692:
5691:
5686:
5681:
5676:
5671:
5666:
5656:
5651:
5646:
5641:
5640:
5639:
5634:
5629:
5624:
5614:
5609:
5607:Formation rule
5604:
5599:
5598:
5597:
5592:
5582:
5581:
5580:
5570:
5565:
5560:
5555:
5549:
5543:
5526:Formal systems
5522:
5521:
5518:
5517:
5515:
5514:
5509:
5504:
5499:
5494:
5489:
5484:
5479:
5474:
5469:
5468:
5467:
5462:
5451:
5449:
5445:
5444:
5442:
5441:
5440:
5439:
5429:
5424:
5423:
5422:
5415:Large cardinal
5412:
5407:
5402:
5397:
5392:
5378:
5377:
5376:
5371:
5366:
5351:
5349:
5339:
5338:
5336:
5335:
5334:
5333:
5328:
5323:
5313:
5308:
5303:
5298:
5293:
5288:
5283:
5278:
5273:
5268:
5263:
5258:
5252:
5250:
5243:
5242:
5240:
5239:
5238:
5237:
5232:
5227:
5222:
5217:
5212:
5204:
5203:
5202:
5197:
5187:
5182:
5180:Extensionality
5177:
5175:Ordinal number
5172:
5162:
5157:
5156:
5155:
5144:
5138:
5132:
5131:
5128:
5127:
5125:
5124:
5119:
5114:
5109:
5104:
5099:
5094:
5093:
5092:
5082:
5081:
5080:
5067:
5065:
5059:
5058:
5056:
5055:
5054:
5053:
5048:
5043:
5033:
5028:
5023:
5018:
5013:
5008:
5002:
5000:
4994:
4993:
4991:
4990:
4985:
4980:
4975:
4970:
4965:
4960:
4959:
4958:
4948:
4943:
4938:
4933:
4928:
4923:
4917:
4915:
4906:
4900:
4899:
4897:
4896:
4891:
4886:
4881:
4876:
4871:
4859:Cantor's
4857:
4852:
4847:
4837:
4835:
4822:
4821:
4819:
4818:
4813:
4808:
4803:
4798:
4793:
4788:
4783:
4778:
4773:
4768:
4763:
4758:
4757:
4756:
4745:
4743:
4739:
4738:
4733:
4731:
4730:
4723:
4716:
4708:
4699:
4698:
4686:
4683:
4682:
4678:
4677:
4675:
4674:
4672:Acyclic finite
4669:
4664:
4659:
4654:
4649:
4644:
4639:
4633:
4628:
4623:
4622:Turing Machine
4617:
4615:Linear-bounded
4612:
4607:
4605:Turing machine
4601:
4599:
4597:
4596:
4591:
4586:
4581:
4576:
4571:
4566:
4564:Tree-adjoining
4561:
4556:
4553:
4548:
4540:
4535:
4530:
4524:
4522:
4520:
4519:
4514:
4511:
4506:
4501:
4496:
4491:
4489:Tree-adjoining
4486:
4481:
4478:
4473:
4465:
4460:
4457:
4451:
4449:
4447:
4446:
4443:
4440:
4437:
4434:
4431:
4428:
4425:
4422:
4419:
4416:
4413:
4410:
4407:
4403:
4400:
4399:
4394:
4389:
4384:
4376:
4373:
4372:
4359:
4357:
4356:
4349:
4342:
4334:
4328:
4327:
4326:
4325:
4319:
4313:
4307:
4301:
4295:
4289:
4283:
4270:
4256:
4247:
4227:
4226:External links
4224:
4222:
4221:
4206:
4184:
4178:
4150:
4140:
4122:
4102:
4101:
4100:
4095:
4094:
4088:
4065:
4064:
4063:
4058:
4055:
4052:
4051:
4039:
4017:
3968:
3962:978-3030409739
3961:
3939:
3926:
3904:
3872:
3865:
3843:
3821:
3810:. January 1992
3799:
3789:
3759:
3758:
3756:
3753:
3751:
3748:
3745:
3744:
3739:
3732:
3725:
3709:
3708:
3706:
3703:
3702:
3701:
3696:
3691:
3686:
3681:
3676:
3669:
3666:
3639:interpretation
3612:
3609:
3574:
3571:
3567:
3543:
3540:
3507:logical system
3441:
3438:
3364:
3361:
3359:
3356:
3355:
3354:
3351:
3350:
3347:
3344:
3341:
3338:
3335:
3332:
3329:
3318:
3315:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3279:
3276:
3266:
3255:
3240:
3239:
3236:
3233:
3230:
3227:
3224:
3221:
3218:
3207:
3204:
3201:
3198:
3195:
3190:
3186:
3182:
3179:
3174:
3170:
3159:
3155:
3154:
3151:
3148:
3145:
3142:
3139:
3136:
3133:
3122:
3119:
3116:
3111:
3108:
3104:
3096:
3092:
3088:
3085:
3081:
3077:
3074:
3069:
3065:
3061:
3056:
3053:
3049:
3038:
3025:
3022:
3018:
3005:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2972:
2967:
2963:
2959:
2956:
2953:
2950:
2947:
2944:
2939:
2935:
2931:
2928:
2921:
2917:
2913:
2908:
2904:
2900:
2895:
2891:
2886:
2882:
2879:
2874:
2870:
2866:
2863:
2853:
2842:
2830:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2808:
2797:
2792:
2788:
2784:
2781:
2778:
2775:
2772:
2769:
2766:
2763:
2760:
2757:
2752:
2748:
2744:
2741:
2731:
2720:
2708:
2707:
2704:
2701:
2698:
2695:
2692:
2689:
2686:
2675:
2670:
2666:
2662:
2659:
2656:
2653:
2650:
2647:
2644:
2641:
2638:
2635:
2630:
2626:
2622:
2619:
2609:
2598:
2586:
2585:
2582:
2579:
2576:
2573:
2570:
2567:
2564:
2553:
2548:
2543:
2539:
2535:
2532:
2529:
2524:
2520:
2516:
2513:
2510:
2507:
2504:
2501:
2498:
2495:
2492:
2489:
2486:
2481:
2476:
2472:
2461:
2457:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2424:
2419:
2415:
2411:
2408:
2405:
2400:
2396:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2369:
2365:
2361:
2356:
2352:
2341:
2335:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2302:
2297:
2293:
2289:
2286:
2283:
2280:
2277:
2274:
2269:
2265:
2261:
2251:
2245:
2244:
2241:
2238:
2235:
2232:
2229:
2226:
2223:
2212:
2207:
2203:
2199:
2196:
2193:
2188:
2184:
2180:
2177:
2174:
2171:
2168:
2165:
2160:
2156:
2152:
2147:
2143:
2132:
2126:
2125:
2122:
2119:
2116:
2113:
2110:
2107:
2104:
2093:
2088:
2084:
2080:
2077:
2074:
2069:
2065:
2061:
2058:
2055:
2052:
2049:
2046:
2041:
2037:
2033:
2028:
2024:
2013:
2007:
2006:
2001:
1996:
1991:
1986:
1981:
1976:
1971:
1969:
1950:
1946:
1923:
1919:
1896:
1892:
1869:
1865:
1822:
1821:
1816:
1815:
1814:
1802:
1799:
1796:
1793:
1790:
1785:
1781:
1777:
1774:
1769:
1765:
1744:
1733:
1719:
1715:
1711:
1706:
1702:
1698:
1693:
1689:
1666:
1662:
1658:
1655:
1652:
1647:
1643:
1620:
1616:
1612:
1607:
1603:
1599:
1596:
1585:
1573:
1570:
1565:
1561:
1539:
1532:
1518:
1514:
1493:
1473:
1451:
1447:
1424:
1420:
1416:
1402:
1388:
1384:
1361:
1357:
1334:
1330:
1326:
1321:
1317:
1302:
1288:
1284:
1263:
1241:
1237:
1216:
1196:
1193:
1171:
1167:
1163:
1158:
1154:
1124:
1102:
1098:
1075:
1071:
1054:
1051:
1018:
1017:
1002:
995:
980:
979:
968:
961:Turing machine
953:
946:
943:formal grammar
933:
930:
929:
928:
916:
913:Turing machine
909:
902:
888:
856:empty language
839:
836:
816:
815:
808:
797:
786:
779:
763:
760:
755:formal grammar
722:
719:
640:
637:
535:
534:
514:
512:
501:
498:
424:formal grammar
399:formal grammar
335:
334:
332:
331:
324:
317:
309:
306:
305:
302:
301:
296:
291:
286:
281:
276:
271:
266:
261:
256:
254:Formal methods
250:
246:
245:
244:
241:
240:
237:
236:
234:Atomic formula
231:
226:
221:
216:
211:
206:
204:Formation rule
201:
199:Formal grammar
196:
191:
186:
181:
176:
170:
166:
165:
164:
161:
160:
154:
153:
139:
138:
53:
51:
44:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
6494:
6483:
6480:
6478:
6475:
6473:
6470:
6469:
6467:
6454:
6453:
6448:
6440:
6434:
6431:
6429:
6426:
6424:
6421:
6419:
6416:
6412:
6409:
6408:
6407:
6404:
6402:
6399:
6397:
6394:
6392:
6388:
6385:
6383:
6380:
6378:
6375:
6373:
6370:
6368:
6365:
6364:
6362:
6358:
6352:
6349:
6347:
6344:
6342:
6341:Recursive set
6339:
6337:
6334:
6332:
6329:
6327:
6324:
6322:
6319:
6315:
6312:
6310:
6307:
6305:
6302:
6300:
6297:
6295:
6292:
6291:
6290:
6287:
6285:
6282:
6280:
6277:
6275:
6272:
6270:
6267:
6265:
6262:
6261:
6259:
6257:
6253:
6247:
6244:
6242:
6239:
6237:
6234:
6232:
6229:
6227:
6224:
6222:
6219:
6217:
6214:
6210:
6207:
6205:
6202:
6200:
6197:
6196:
6195:
6192:
6190:
6187:
6185:
6182:
6180:
6177:
6175:
6172:
6170:
6167:
6163:
6160:
6159:
6158:
6155:
6151:
6150:of arithmetic
6148:
6147:
6146:
6143:
6139:
6136:
6134:
6131:
6129:
6126:
6124:
6121:
6119:
6116:
6115:
6114:
6111:
6107:
6104:
6102:
6099:
6098:
6097:
6094:
6093:
6091:
6089:
6085:
6079:
6076:
6074:
6071:
6069:
6066:
6064:
6061:
6058:
6057:from ZFC
6054:
6051:
6049:
6046:
6040:
6037:
6036:
6035:
6032:
6030:
6027:
6025:
6022:
6021:
6020:
6017:
6015:
6012:
6010:
6007:
6005:
6002:
6000:
5997:
5995:
5992:
5990:
5987:
5986:
5984:
5982:
5978:
5968:
5967:
5963:
5962:
5957:
5956:non-Euclidean
5954:
5950:
5947:
5945:
5942:
5940:
5939:
5935:
5934:
5932:
5929:
5928:
5926:
5922:
5918:
5915:
5913:
5910:
5909:
5908:
5904:
5900:
5897:
5896:
5895:
5891:
5887:
5884:
5882:
5879:
5877:
5874:
5872:
5869:
5867:
5864:
5862:
5859:
5858:
5856:
5852:
5851:
5849:
5844:
5838:
5833:Example
5830:
5822:
5817:
5816:
5815:
5812:
5810:
5807:
5803:
5800:
5798:
5795:
5793:
5790:
5788:
5785:
5784:
5783:
5780:
5778:
5775:
5773:
5770:
5768:
5765:
5761:
5758:
5756:
5753:
5752:
5751:
5748:
5744:
5741:
5739:
5736:
5734:
5731:
5729:
5726:
5725:
5724:
5721:
5719:
5716:
5712:
5709:
5707:
5704:
5702:
5699:
5698:
5697:
5694:
5690:
5687:
5685:
5682:
5680:
5677:
5675:
5672:
5670:
5667:
5665:
5662:
5661:
5660:
5657:
5655:
5652:
5650:
5647:
5645:
5642:
5638:
5635:
5633:
5630:
5628:
5625:
5623:
5620:
5619:
5618:
5615:
5613:
5610:
5608:
5605:
5603:
5600:
5596:
5593:
5591:
5590:by definition
5588:
5587:
5586:
5583:
5579:
5576:
5575:
5574:
5571:
5569:
5566:
5564:
5561:
5559:
5556:
5554:
5551:
5550:
5547:
5544:
5542:
5538:
5533:
5527:
5523:
5513:
5510:
5508:
5505:
5503:
5500:
5498:
5495:
5493:
5490:
5488:
5485:
5483:
5480:
5478:
5477:Kripke–Platek
5475:
5473:
5470:
5466:
5463:
5461:
5458:
5457:
5456:
5453:
5452:
5450:
5446:
5438:
5435:
5434:
5433:
5430:
5428:
5425:
5421:
5418:
5417:
5416:
5413:
5411:
5408:
5406:
5403:
5401:
5398:
5396:
5393:
5390:
5386:
5382:
5379:
5375:
5372:
5370:
5367:
5365:
5362:
5361:
5360:
5356:
5353:
5352:
5350:
5348:
5344:
5340:
5332:
5329:
5327:
5324:
5322:
5321:constructible
5319:
5318:
5317:
5314:
5312:
5309:
5307:
5304:
5302:
5299:
5297:
5294:
5292:
5289:
5287:
5284:
5282:
5279:
5277:
5274:
5272:
5269:
5267:
5264:
5262:
5259:
5257:
5254:
5253:
5251:
5249:
5244:
5236:
5233:
5231:
5228:
5226:
5223:
5221:
5218:
5216:
5213:
5211:
5208:
5207:
5205:
5201:
5198:
5196:
5193:
5192:
5191:
5188:
5186:
5183:
5181:
5178:
5176:
5173:
5171:
5167:
5163:
5161:
5158:
5154:
5151:
5150:
5149:
5146:
5145:
5142:
5139:
5137:
5133:
5123:
5120:
5118:
5115:
5113:
5110:
5108:
5105:
5103:
5100:
5098:
5095:
5091:
5088:
5087:
5086:
5083:
5079:
5074:
5073:
5072:
5069:
5068:
5066:
5064:
5060:
5052:
5049:
5047:
5044:
5042:
5039:
5038:
5037:
5034:
5032:
5029:
5027:
5024:
5022:
5019:
5017:
5014:
5012:
5009:
5007:
5004:
5003:
5001:
4999:
4998:Propositional
4995:
4989:
4986:
4984:
4981:
4979:
4976:
4974:
4971:
4969:
4966:
4964:
4961:
4957:
4954:
4953:
4952:
4949:
4947:
4944:
4942:
4939:
4937:
4934:
4932:
4929:
4927:
4926:Logical truth
4924:
4922:
4919:
4918:
4916:
4914:
4910:
4907:
4905:
4901:
4895:
4892:
4890:
4887:
4885:
4882:
4880:
4877:
4875:
4872:
4870:
4866:
4862:
4858:
4856:
4853:
4851:
4848:
4846:
4842:
4839:
4838:
4836:
4834:
4828:
4823:
4817:
4814:
4812:
4809:
4807:
4804:
4802:
4799:
4797:
4794:
4792:
4789:
4787:
4784:
4782:
4779:
4777:
4774:
4772:
4769:
4767:
4764:
4762:
4759:
4755:
4752:
4751:
4750:
4747:
4746:
4744:
4740:
4736:
4729:
4724:
4722:
4717:
4715:
4710:
4709:
4706:
4691:
4690:proper subset
4684:
4673:
4670:
4668:
4665:
4663:
4660:
4658:
4655:
4653:
4650:
4648:
4645:
4643:
4640:
4638:
4634:
4632:
4629:
4627:
4624:
4621:
4618:
4616:
4613:
4611:
4608:
4606:
4603:
4602:
4600:
4595:
4592:
4590:
4587:
4585:
4582:
4580:
4577:
4575:
4572:
4570:
4567:
4565:
4562:
4560:
4557:
4554:
4552:
4549:
4546:
4541:
4539:
4536:
4534:
4531:
4529:
4526:
4525:
4523:
4518:
4517:Non-recursive
4515:
4512:
4510:
4507:
4505:
4502:
4500:
4497:
4495:
4492:
4490:
4487:
4485:
4482:
4479:
4477:
4474:
4471:
4466:
4464:
4461:
4458:
4456:
4453:
4452:
4450:
4444:
4441:
4438:
4435:
4432:
4429:
4426:
4423:
4420:
4417:
4414:
4411:
4408:
4405:
4404:
4402:
4401:
4398:
4395:
4393:
4390:
4388:
4385:
4383:
4380:
4379:
4374:
4370:
4366:
4362:
4355:
4350:
4348:
4343:
4341:
4336:
4335:
4332:
4324:
4320:
4318:
4314:
4312:
4308:
4306:
4302:
4300:
4296:
4294:
4290:
4288:
4284:
4282:
4278:
4277:
4275:
4271:
4268:
4264:
4261:
4258:James Power,
4257:
4255:
4251:
4248:
4244:
4240:
4239:
4234:
4230:
4229:
4225:
4219:
4218:0-442-08072-7
4215:
4211:
4207:
4204:
4203:3-540-61486-9
4200:
4196:
4192:
4188:
4185:
4181:
4175:
4171:
4167:
4163:
4159:
4155:
4151:
4148:
4144:
4141:
4138:
4137:0-7204-2506-9
4134:
4130:
4126:
4123:
4120:
4119:0-521-21838-1
4116:
4112:
4108:
4104:
4103:
4098:
4097:
4091:
4089:81-7808-347-7
4085:
4081:
4080:
4075:
4071:
4067:
4066:
4061:
4060:
4056:
4048:
4043:
4040:
4027:
4021:
4018:
4013:
4009:
4004:
3999:
3995:
3991:
3987:
3983:
3979:
3972:
3969:
3964:
3958:
3954:
3950:
3943:
3940:
3936:
3930:
3927:
3914:
3908:
3905:
3889:
3882:
3876:
3873:
3868:
3862:
3858:
3854:
3847:
3844:
3831:
3825:
3822:
3809:
3803:
3800:
3796:
3792:
3790:9781848820500
3786:
3782:
3778:
3774:
3773:
3764:
3761:
3754:
3749:
3738:
3731:
3724:
3720:
3717:For example,
3714:
3711:
3704:
3700:
3697:
3695:
3692:
3690:
3687:
3685:
3682:
3680:
3679:Formal method
3677:
3675:
3672:
3671:
3667:
3665:
3663:
3659:
3655:
3651:
3646:
3644:
3640:
3636:
3632:
3626:
3622:
3618:
3610:
3608:
3606:
3602:
3598:
3594:
3589:
3572:
3528:
3524:
3520:
3516:
3512:
3508:
3504:
3500:
3499:formal system
3495:
3493:
3489:
3488:formal theory
3485:
3477:
3473:
3469:
3465:
3464:formal system
3461:
3456:
3451:
3450:Formal system
3447:
3439:
3437:
3435:
3431:
3427:
3423:
3419:
3414:
3411:
3406:
3402:
3398:
3394:
3390:
3386:
3380:
3374:
3370:
3362:
3357:
3348:
3345:
3342:
3339:
3336:
3333:
3330:
3313:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3289:
3283:
3280:
3277:
3274:
3267:
3253:
3246:
3242:
3241:
3237:
3234:
3231:
3228:
3225:
3222:
3219:
3202:
3199:
3196:
3193:
3188:
3184:
3177:
3172:
3168:
3160:
3157:
3156:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3117:
3109:
3106:
3102:
3094:
3090:
3086:
3083:
3079:
3075:
3067:
3063:
3054:
3051:
3047:
3039:
3023:
3020:
3016:
3007:
3006:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2965:
2961:
2954:
2951:
2948:
2945:
2937:
2933:
2926:
2919:
2915:
2911:
2906:
2902:
2898:
2893:
2889:
2884:
2880:
2872:
2868:
2861:
2854:
2840:
2833:Substitution
2832:
2831:
2827:
2824:
2821:
2818:
2815:
2812:
2809:
2790:
2786:
2782:
2779:
2776:
2770:
2764:
2758:
2750:
2746:
2739:
2732:
2718:
2710:
2709:
2705:
2702:
2699:
2696:
2693:
2690:
2687:
2668:
2664:
2660:
2657:
2654:
2648:
2642:
2636:
2628:
2624:
2617:
2610:
2596:
2588:
2587:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2546:
2541:
2537:
2533:
2530:
2527:
2522:
2518:
2514:
2511:
2508:
2505:
2502:
2496:
2490:
2484:
2479:
2474:
2470:
2462:
2459:
2458:
2454:
2451:
2448:
2445:
2442:
2439:
2436:
2417:
2413:
2409:
2406:
2403:
2398:
2394:
2390:
2387:
2384:
2381:
2378:
2372:
2367:
2363:
2359:
2354:
2350:
2342:
2340:
2339:Concatenation
2337:
2336:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2295:
2291:
2287:
2284:
2281:
2278:
2272:
2267:
2263:
2252:
2250:
2247:
2246:
2242:
2239:
2236:
2233:
2230:
2227:
2224:
2205:
2201:
2197:
2194:
2191:
2186:
2182:
2178:
2175:
2172:
2169:
2163:
2158:
2154:
2150:
2145:
2141:
2133:
2131:
2128:
2127:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2086:
2082:
2078:
2075:
2072:
2067:
2063:
2059:
2056:
2053:
2050:
2044:
2039:
2035:
2031:
2026:
2022:
2014:
2012:
2009:
2008:
2005:
2002:
2000:
1997:
1995:
1992:
1990:
1987:
1985:
1982:
1980:
1977:
1975:
1972:
1970:
1967:
1966:
1948:
1944:
1921:
1917:
1894:
1890:
1867:
1863:
1852:
1851:
1850:
1848:
1844:
1840:
1836:
1831:
1827:
1820:
1817:
1797:
1794:
1791:
1788:
1783:
1779:
1772:
1767:
1763:
1742:
1734:
1717:
1713:
1709:
1704:
1700:
1696:
1691:
1687:
1664:
1660:
1656:
1653:
1650:
1645:
1641:
1618:
1614:
1610:
1605:
1601:
1597:
1594:
1586:
1571:
1568:
1563:
1559:
1550:
1546:
1545:
1543:
1540:
1537:
1533:
1516:
1512:
1449:
1445:
1422:
1418:
1407:
1403:
1386:
1382:
1359:
1355:
1332:
1328:
1324:
1319:
1315:
1307:
1303:
1286:
1282:
1261:
1239:
1235:
1214:
1194:
1191:
1169:
1165:
1161:
1156:
1152:
1144:
1143:
1142:concatenation
1138:
1137:
1136:
1100:
1096:
1073:
1069:
1059:
1052:
1050:
1048:
1044:
1040:
1036:
1032:
1028:
1024:
1015:
1011:
1007:
1003:
1000:
996:
993:
989:
985:
984:
983:
977:
973:
969:
966:
962:
958:
954:
951:
947:
944:
940:
939:
938:
931:
924:
921:
917:
914:
910:
907:
903:
900:
896:
889:
887:words over Σ;
886:
879:
878:
877:
875:
869:
866:
863: =
857:
853:
838:Constructions
837:
835:
833:
829:
825:
809:
798:
787:
780:
773:
772:
771:
761:
759:
756:
752:
748:
742:
740:
735:
732:
728:
720:
718:
716:
712:
708:
704:
699:
697:
696:concatenation
693:
689:
685:
681:
676:
674:
670:
666:
662:
658:
654:
650:
646:
638:
636:
634:
630:
626:
622:
618:
614:
610:
608:
604:
603:Heinz Zemanek
600:
596:
591:
589:
585:
581:
577:
572:
570:
569:
564:
563:Gottlob Frege
560:
558:
554:
550:
546:
542:
531:
522:
518:
515:This section
513:
510:
506:
505:
499:
497:
495:
491:
487:
484:The field of
482:
480:
476:
472:
468:
464:
460:
456:
452:
448:
444:
439:
437:
433:
429:
425:
421:
420:
415:
411:
407:
402:
400:
396:
392:
388:
384:
380:
376:
372:
368:
364:
356:
352:
348:
343:
339:
330:
325:
323:
318:
316:
311:
310:
308:
307:
300:
297:
295:
292:
290:
287:
285:
282:
280:
277:
275:
272:
270:
267:
265:
262:
260:
257:
255:
252:
251:
243:
242:
235:
232:
230:
227:
225:
222:
220:
217:
215:
212:
210:
207:
205:
202:
200:
197:
195:
192:
190:
187:
185:
182:
180:
177:
175:
174:Formal system
172:
171:
163:
162:
159:
155:
151:
150:
145:
144:
135:
132:
124:
113:
110:
106:
103:
99:
96:
92:
89:
85:
82: –
81:
77:
76:Find sources:
70:
66:
60:
59:
54:This article
52:
48:
43:
42:
37:
33:
19:
6443:
6241:Ultraproduct
6088:Model theory
6053:Independence
5989:Formal proof
5981:Proof theory
5964:
5937:
5894:real numbers
5866:second-order
5777:Substitution
5654:Metalanguage
5648:
5595:conservative
5568:Axiom schema
5536:
5512:Constructive
5482:Morse–Kelley
5448:Set theories
5427:Aleph number
5420:inaccessible
5326:Grothendieck
5210:intersection
5097:Higher-order
5085:Second-order
5031:Truth tables
4988:Venn diagram
4771:Formal proof
4626:Nested stack
4569:Context-free
4494:Context-free
4455:Unrestricted
4391:
4364:
4236:
4209:
4194:
4191:Arto Salomaa
4157:
4146:
4128:
4106:
4077:
4042:
4030:. Retrieved
4020:
3985:
3981:
3971:
3952:
3942:
3929:
3917:. Retrieved
3907:
3895:. Retrieved
3875:
3856:
3846:
3834:. Retrieved
3824:
3812:. Retrieved
3802:
3794:
3771:
3763:
3736:
3729:
3722:
3713:
3661:
3654:model theory
3647:
3628:
3625:Model theory
3601:propositions
3596:
3593:formal proof
3592:
3590:
3514:
3506:
3502:
3498:
3496:
3490:is a set of
3487:
3481:
3436:to execute.
3426:machine code
3415:
3376:
3358:Applications
2460:Kleene star
2130:Intersection
1823:
1548:
1541:
1405:
1306:intersection
1305:
1140:
1060:
1056:
1019:
1013:
1009:
1005:
998:
991:
987:
981:
959:, such as a
935:
920:alphanumeric
898:
894:
884:
873:
870:
855:
841:
817:
765:
743:
736:
726:
724:
714:
710:
706:
700:
691:
679:
677:
652:
644:
642:
613:Noam Chomsky
611:
592:
573:
566:
561:
538:
525:
521:adding to it
516:
485:
483:
440:
417:
413:
403:
381:consists of
378:
360:
346:
338:
247:Applications
167:Key concepts
148:
127:
118:
108:
101:
94:
87:
75:
63:Please help
58:verification
55:
6351:Type theory
6299:undecidable
6231:Truth value
6118:equivalence
5797:non-logical
5410:Enumeration
5400:Isomorphism
5347:cardinality
5331:Von Neumann
5296:Ultrafilter
5261:Uncountable
5195:equivalence
5112:Quantifiers
5102:Fixed-point
5071:First-order
4951:Consistency
4936:Proposition
4913:Traditional
4884:Lindström's
4874:Compactness
4816:Type theory
4761:Cardinality
4635:restricted
4062:Works cited
3684:Free monoid
3643:truth value
3424:containing
3389:identifiers
1909:where both
1536:Kleene star
688:Kleene star
621:John Backus
557:Gauss codes
549:pictographs
395:well-formed
375:linguistics
367:mathematics
6466:Categories
6162:elementary
5855:arithmetic
5723:Quantifier
5701:functional
5573:Expression
5291:Transitive
5235:identities
5220:complement
5153:hereditary
5136:Set theory
4285:Sheng Yu,
4276:, (1997):
3750:References
3597:derivation
3422:executable
2249:Complement
1968:Operation
1406:complement
852:degenerate
721:Definition
707:vocabulary
692:empty word
629:Peter Naur
619:. In 1959
528:March 2021
426:such as a
224:Production
121:March 2024
91:newspapers
6433:Supertask
6336:Recursion
6294:decidable
6128:saturated
6106:of models
6029:deductive
6024:axiomatic
5944:Hilbert's
5931:Euclidean
5912:canonical
5835:axiomatic
5767:Signature
5696:Predicate
5585:Extension
5507:Ackermann
5432:Operation
5311:Universal
5301:Recursive
5276:Singleton
5271:Inhabited
5256:Countable
5246:Types of
5230:power set
5200:partition
5117:Predicate
5063:Predicate
4978:Syllogism
4968:Soundness
4941:Inference
4931:Tautology
4833:paradoxes
4589:Star-free
4543:Positive
4533:Decidable
4468:Positive
4392:Languages
4243:EMS Press
3767:See e.g.
3755:Citations
3631:semantics
3492:sentences
3460:syntactic
3311:∈
3305:∧
3299:∈
3293:∣
3278:∩
3200:∈
3194:∣
3107:−
3087:∈
3080:⋃
3052:−
3021:−
2962:σ
2955:φ
2952:⋅
2949:…
2946:⋅
2934:σ
2927:φ
2912:∈
2903:σ
2899:⋯
2890:σ
2885:⋃
2862:φ
2841:φ
2783:∈
2777:∣
2661:∈
2655:∣
2547:∗
2534:∈
2528:∧
2515:∈
2509:∣
2497:∪
2491:ε
2480:∗
2410:∈
2404:∧
2391:∈
2385:∣
2360:⋅
2282:∣
2260:¬
2198:∈
2192:∧
2179:∈
2173:∣
2151:∩
2079:∈
2073:∨
2060:∈
2054:∣
2032:∪
1999:recursive
1795:∈
1789:∣
1714:σ
1710:⋯
1701:σ
1661:σ
1654:…
1642:σ
1615:σ
1611:⋯
1602:σ
1572:ε
1560:ε
1492:Σ
1472:Σ
1415:¬
1325:∩
1162:⋅
1123:Σ
1035:automaton
976:algorithm
957:automaton
915:halts; or
832:semantics
715:sentences
593:In 1907,
580:Emil Post
576:Axel Thue
551:. Later,
490:syntactic
447:semantics
6418:Logicism
6411:timeline
6387:Concrete
6246:Validity
6216:T-schema
6209:Kripke's
6204:Tarski's
6199:semantic
6189:Strength
6138:submodel
6133:spectrum
6101:function
5949:Tarski's
5938:Elements
5925:geometry
5881:Robinson
5802:variable
5787:function
5760:spectrum
5750:Sentence
5706:variable
5649:Language
5602:Relation
5563:Automata
5553:Alphabet
5537:language
5391:-jection
5369:codomain
5355:Function
5316:Universe
5286:Infinite
5190:Relation
4973:Validity
4963:Argument
4861:theorem,
4387:Grammars
4263:Archived
4156:(2010).
4113:, 1978,
4076:(1979).
4032:30 April
4012:22688632
3919:30 April
3897:30 April
3888:Archived
3836:30 April
3814:30 April
3668:See also
3573:′
3476:theorems
3393:keywords
3158:Reverse
2288:∉
1542:Reversal
1012:, or in
846:as just
762:Examples
711:formulas
667:such as
661:alphabet
657:infinite
645:alphabet
469:and the
393:and are
391:alphabet
179:Alphabet
149:a series
146:Part of
6360:Related
6157:Diagram
6055: (
6034:Hilbert
6019:Systems
6014:Theorem
5892:of the
5837:systems
5617:Formula
5612:Grammar
5528: (
5472:General
5185:Forcing
5170:Element
5090:Monadic
4865:paradox
4806:Theorem
4742:General
4610:Decider
4584:Regular
4551:Indexed
4509:Regular
4476:Indexed
4245:, 2001
4057:Sources
4003:3367686
3777:Bibcode
3735:,
3728:,
3505:, or a
1974:Regular
1633:(where
1047:parsing
673:Unicode
653:letters
625:FORTRAN
500:History
410:strings
387:letters
355:Chomsky
105:scholar
6123:finite
5886:Skolem
5839:
5814:Theory
5782:Symbol
5772:String
5755:atomic
5632:ground
5627:closed
5622:atomic
5578:ground
5541:syntax
5437:binary
5364:domain
5281:Finite
5046:finite
4904:Logics
4863:
4811:Theory
4662:Finite
4594:Finite
4439:Type-3
4430:Type-2
4412:Type-1
4406:Type-0
4216:
4201:
4176:
4135:
4117:
4086:
4010:
4000:
3959:
3863:
3787:
3623:, and
3527:derive
3523:axioms
3401:parser
1207:where
828:syntax
731:subset
684:string
599:Vienna
477:, and
406:tokens
385:whose
373:, and
184:Syntax
107:
100:
93:
86:
78:
6113:Model
5861:Peano
5718:Proof
5558:Arity
5487:Naive
5374:image
5306:Fuzzy
5266:Empty
5215:union
5160:Class
4801:Model
4791:Lemma
4749:Axiom
4620:PTIME
3891:(PDF)
3884:(PDF)
3705:Notes
3662:model
3635:logic
3407:like
2011:Union
1843:trios
1824:Such
1584:, and
923:ASCII
703:logic
669:ASCII
467:logic
449:. In
383:words
363:logic
357:1957)
353:from
112:JSTOR
98:books
6236:Type
6039:list
5843:list
5820:list
5809:Term
5743:rank
5637:open
5531:list
5343:Maps
5248:sets
5107:Free
5077:list
4827:list
4754:list
4367:and
4214:ISBN
4199:ISBN
4174:ISBN
4133:ISBN
4115:ISBN
4084:ISBN
4034:2021
4008:PMID
3957:ISBN
3921:2021
3899:2021
3861:ISBN
3838:2021
3816:2021
3785:ISBN
3556:and
3486:, a
3448:and
3410:yacc
3371:and
3349:Yes
3346:Yes
3343:Yes
3340:Yes
3337:Yes
3334:Yes
3331:Yes
3238:Yes
3235:Yes
3232:Yes
3229:Yes
3226:Yes
3220:Yes
3153:Yes
3150:Yes
3147:Yes
3144:Yes
3141:Yes
3138:Yes
3135:Yes
3003:Yes
2997:Yes
2994:Yes
2991:Yes
2985:Yes
2828:Yes
2825:Yes
2822:Yes
2819:Yes
2816:Yes
2810:Yes
2706:Yes
2697:Yes
2694:Yes
2688:Yes
2584:Yes
2581:Yes
2578:Yes
2575:Yes
2572:Yes
2566:Yes
2455:Yes
2452:Yes
2449:Yes
2446:Yes
2443:Yes
2437:Yes
2330:Yes
2327:Yes
2318:Yes
2315:Yes
2243:Yes
2240:Yes
2237:Yes
2225:Yes
2124:Yes
2121:Yes
2118:Yes
2115:Yes
2112:Yes
2106:Yes
1979:DCFL
1936:and
1845:and
1547:Let
1534:The
1404:The
1374:and
1304:The
1254:and
1139:The
1088:and
1041:and
1025:and
974:(an
680:word
377:, a
84:news
5923:of
5905:of
5853:of
5385:Sur
5359:Map
5166:Ur-
5148:Set
4166:doi
3998:PMC
3990:doi
3986:367
3595:or
3482:In
3391:or
3384:lex
3223:No
3000:No
2988:No
2813:No
2703:No
2700:No
2691:No
2569:No
2440:No
2333:No
2324:No
2321:No
2234:No
2231:No
2228:No
2109:No
1994:CSL
1989:IND
1984:CFL
1882:Op
1437:of
1347:of
963:or
885:all
868:).
749:or
713:or
671:or
649:set
643:An
523:.
430:or
416:or
361:In
67:by
6468::
6309:NP
5933::
5927::
5857::
5534:),
5389:Bi
5381:In
4363::
4252:,
4241:,
4235:,
4193:,
4189:,
4172:.
4164:.
4145:,
4127:,
4109:,
4072:;
4006:.
3996:.
3984:.
3980:.
3951:.
3793:.
3783:.
3645:.
3619:,
3591:A
3497:A
3466:.
2004:RE
1755:,
1544::
1135:.
1037:.
1001:?)
908:);
678:A
675:.
627:.
559:.
496:.
453:,
438:.
401:.
369:,
365:,
152:on
6389:/
6304:P
6059:)
5845:)
5841:(
5738:∀
5733:!
5728:∃
5689:=
5684:↔
5679:→
5674:∧
5669:∨
5664:¬
5387:/
5383:/
5357:/
5168:)
5164:(
5051:∞
5041:3
4829:)
4727:e
4720:t
4713:v
4555:—
4513:—
4480:—
4445:—
4442:—
4436:—
4433:—
4427:—
4424:—
4421:—
4418:—
4415:—
4409:—
4353:e
4346:t
4339:v
4220:.
4205:.
4182:.
4168::
4139:.
4121:.
4092:.
4036:.
4014:.
3992::
3965:.
3923:.
3901:.
3869:.
3840:.
3818:.
3779::
3740:2
3737:x
3733:1
3730:x
3726:0
3723:x
3570:S
3566:F
3542:S
3539:F
3317:}
3314:R
3308:w
3302:L
3296:w
3290:w
3287:{
3284:=
3281:R
3275:L
3254:R
3206:}
3203:L
3197:w
3189:R
3185:w
3181:{
3178:=
3173:R
3169:L
3121:)
3118:w
3115:(
3110:1
3103:h
3095:1
3091:L
3084:w
3076:=
3073:)
3068:1
3064:L
3060:(
3055:1
3048:h
3024:1
3017:h
2971:)
2966:n
2958:(
2943:)
2938:1
2930:(
2920:1
2916:L
2907:n
2894:1
2881:=
2878:)
2873:1
2869:L
2865:(
2796:}
2791:1
2787:L
2780:w
2774:)
2771:w
2768:(
2765:h
2762:{
2759:=
2756:)
2751:1
2747:L
2743:(
2740:h
2719:h
2674:}
2669:1
2665:L
2658:w
2652:)
2649:w
2646:(
2643:h
2640:{
2637:=
2634:)
2629:1
2625:L
2621:(
2618:h
2597:h
2552:}
2542:1
2538:L
2531:z
2523:1
2519:L
2512:w
2506:z
2503:w
2500:{
2494:}
2488:{
2485:=
2475:1
2471:L
2423:}
2418:2
2414:L
2407:z
2399:1
2395:L
2388:w
2382:z
2379:w
2376:{
2373:=
2368:2
2364:L
2355:1
2351:L
2301:}
2296:1
2292:L
2285:w
2279:w
2276:{
2273:=
2268:1
2264:L
2211:}
2206:2
2202:L
2195:w
2187:1
2183:L
2176:w
2170:w
2167:{
2164:=
2159:2
2155:L
2146:1
2142:L
2092:}
2087:2
2083:L
2076:w
2068:1
2064:L
2057:w
2051:w
2048:{
2045:=
2040:2
2036:L
2027:1
2023:L
1949:2
1945:L
1922:1
1918:L
1895:2
1891:L
1868:1
1864:L
1813:.
1801:}
1798:L
1792:w
1784:R
1780:w
1776:{
1773:=
1768:R
1764:L
1743:L
1732:,
1718:1
1705:n
1697:=
1692:R
1688:w
1665:n
1657:,
1651:,
1646:1
1619:n
1606:1
1598:=
1595:w
1569:=
1564:R
1549:ε
1531:.
1517:1
1513:L
1450:1
1446:L
1423:1
1419:L
1387:2
1383:L
1360:1
1356:L
1333:2
1329:L
1320:1
1316:L
1301:.
1287:2
1283:L
1262:w
1240:1
1236:L
1215:v
1195:w
1192:v
1170:2
1166:L
1157:1
1153:L
1101:2
1097:L
1074:1
1070:L
1014:X
1010:Y
1006:X
999:X
992:Y
988:X
967:;
952:;
945:;
899:n
895:n
891:L
881:L
874:L
865:∅
861:L
848:L
844:L
820:L
812:L
807:.
805:L
801:L
796:.
794:L
790:L
785:.
783:L
778:.
776:L
768:L
727:L
530:)
526:(
349:(
328:e
321:t
314:v
134:)
128:(
123:)
119:(
109:·
102:·
95:·
88:·
61:.
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
