Theory: Difference between revisions
| Line 23: | Line 23: | ||
===Context-Sensitive Languages=== | ===Context-Sensitive Languages=== | ||
* Type 1 of the [[Chomsky Hierarchy]], a proper superset of | * Type 1 of the [[Chomsky Hierarchy]], a proper superset of CFLs | ||
* Recognized by linear bounded automata | * Recognized by linear bounded automata | ||
===Recursively-Enumerable Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re RE])=== | ===Recursively-Enumerable Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re RE])=== | ||
* Type 0 of the [[Chomsky Hierarchy]], a proper superset of | * Type 0 of the [[Chomsky Hierarchy]], a proper superset of CSLs | ||
* 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) | ||