Theory: Difference between revisions
No edit summary |
|||
| Line 20: | Line 20: | ||
* Not closed under complement or difference | * Not closed under complement or difference | ||
* 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 | |||
====Efficiently-Parsed CFLs==== | ====Efficiently-Parsed CFLs==== | ||
* LL(''n'') (Lewis and Stearns, 1968): | * LL(''n'') (Lewis and Stearns, 1968): | ||
| Line 35: | Line 37: | ||
===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]] | ||