Theory: Difference between revisions
| Line 20: | Line 20: | ||
* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection | * The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection | ||
* Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input CFLs | * Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input CFLs | ||
====Efficiently-Parsed CFLs==== | ====Efficiently-Parsed CFLs (using ''n'' tokens of lookahead)==== | ||
* LL(''n'') (Lewis and Stearns, 1968): | * LL(''n'') (Lewis and Stearns, 1968): | ||
** Language equality is decidable for the ''simple grammars'', a subset of LL(1) | ** Language equality is decidable for the ''simple grammars'', a subset of LL(1) | ||
* LR(''n'') (Knuth, 1965): | * LR(''n'') (Knuth, 1965): | ||
* LALR(''n''): | * LALR(''n''): | ||
===Context-Sensitive Languages=== | ===Context-Sensitive Languages=== | ||
* Type 1 of the [[Chomsky Hierarchy]], and a proper superset of CFLs | * Type 1 of the [[Chomsky Hierarchy]], and a proper superset of CFLs | ||