Theory: Difference between revisions
| Line 1: | Line 1: | ||
==Formal Languages== | ==Formal Languages== | ||
===Regular Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#reg REG])=== | ===Regular Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#reg REG])=== | ||
* Type 3 of the Chomsky Hierarchy | * Type 3 of the [[Chomsky Hierarchy]] | ||
* Recognized by finite state machines. Equivalent to [http://qwiki.stanford.edu/wiki/Complexity_Zoo:D#dspace DSPACE(1)]. | * Recognized by finite state machines. Equivalent to [http://qwiki.stanford.edu/wiki/Complexity_Zoo:D#dspace DSPACE(1)]. | ||
* Closed under union, concatenation, Kleene, intersection, difference, complement, reverse, right-quotient, homomorphism | * Closed under union, concatenation, Kleene, intersection, difference, complement, reverse, right-quotient, homomorphism | ||
| Line 11: | Line 11: | ||
===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ||
* Type 2 of the Chomsky Hierarchy, a proper superset of RL's | * Type 2 of the [[Chomsky Hierarchy]], a proper superset of RL's | ||
* Recognized by nondeterministic pushdown automata | * Recognized by nondeterministic pushdown automata | ||
** Deterministic pushdown automata cannot recognize all CFL's! | ** Deterministic pushdown automata cannot recognize all CFL's! | ||
| Line 21: | Line 21: | ||
* LR(''n'') (Knuth, 1965): | * LR(''n'') (Knuth, 1965): | ||
===Context-Sensitive Languages=== | ===Context-Sensitive Languages=== | ||
* Type 1 of the Chomsky Hierarchy, a proper superset of CFL's | * Type 1 of the [[Chomsky Hierarchy]], a proper superset of CFL's | ||
* 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 CSL's | * Type 0 of the [[Chomsky Hierarchy]], a proper superset of CSL's | ||
* Recognized by Turing Machines | * Recognized by [[Turing Machines]] | ||
===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])=== | |||
* Decided by [[Turing Machines]] | |||
[[Category: CS GRE Prep]] | [[Category: CS GRE Prep]] | ||