Theory: Difference between revisions
| Line 11: | Line 11: | ||
** |''y''| ≥ 1, and | ** |''y''| ≥ 1, and | ||
** ''xy<sup>i</sup>z'' ∈ '''L''' for all ''i'' ≥ 0 | ** ''xy<sup>i</sup>z'' ∈ '''L''' for all ''i'' ≥ 0 | ||
===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ||
* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs | * Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs | ||
| Line 21: | 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 input CFLs | * Universality, language equality, language inclusion, and regularity are all undecidable given input CFLs | ||
====Efficiently-Parsed CFLs==== | ====Efficiently-Parsed CFLs==== | ||
* LL(''n'') (Lewis and Stearns, 1968): | * LL(''n'') (Lewis and Stearns, 1968): | ||
| Line 27: | Line 25: | ||
* 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 | ||
| Line 37: | Line 33: | ||
* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals | * Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals | ||
* Recognized by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt) | * Recognized by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt) | ||
===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])=== | ===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])=== | ||
* Decided by [[Turing Machines]] | * Decided by [[Turing Machines]] | ||
[[Category: CS GRE Prep]] | [[Category: CS GRE Prep]] | ||