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]] | ||
* Rewrite rules: A→a and A→aB, where {A, B} are non-terminals, and a is a terminal | |||
* Nondeterminism (NFAs) adds no power to finite state automata (DFAs). | * Nondeterminism (NFAs) adds no power to finite state automata (DFAs). | ||
* 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)]. | ||
| Line 12: | Line 13: | ||
===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ===Context-Free Languages (CFLs) / Grammars (CFGs)=== | ||
* Type 2 of the [[Chomsky Hierarchy]], a proper superset of RLs | * Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs | ||
* Rewrite rule: A→γ, where A is a non-terminal, and γ is a string of terminals and non-terminals | |||
* Recognized by nondeterministic pushdown automata | * Recognized by nondeterministic pushdown automata | ||
** Deterministic pushdown automata (DPDAs) cannot recognize all CFLs (only the DCFLs)! | ** Deterministic pushdown automata (DPDAs) cannot recognize all CFLs (only the DCFLs)! | ||
| Line 23: | Line 25: | ||
===Context-Sensitive Languages=== | ===Context-Sensitive Languages=== | ||
* Type 1 of the [[Chomsky Hierarchy]], a proper superset of CFLs | * Type 1 of the [[Chomsky Hierarchy]], and a proper superset of CFLs | ||
* Rewrite rule: αAβ→αγβ, where A is a non-terminal, and {α, β, γ} are strings of terminals and non-terminals | |||
* 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 CSLs | * Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs | ||
* 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) | ||