Theory: Difference between revisions
| Line 2: | Line 2: | ||
===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]] (rewrite rules: A→a and A→aB) | * Type 3 of the [[Chomsky Hierarchy]] (rewrite rules: A→a and A→aB) | ||
* 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)]. | ||
* 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 9: | Line 10: | ||
** |''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)=== | ||