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