Theory: Difference between revisions
| Line 5: | Line 5: | ||
* 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)]. | ||
* Closed under union, concatenation, Kleene, intersection, difference, complement, reverse, right-quotient, homomorphism | * Closed under union, concatenation, Kleene, intersection, difference, complement, reverse, right-quotient, homomorphism, derivation | ||
** Derivation with respect to '''L''' and a: all the strings in L starting with 'a' have it removed | |||
* Pumping lemma: A language '''L''' is regular if and only if there exists a positive integer ''m'' such that for any ''w'' ∈ '''L''' with |''w''| ≥ ''m'' there exist strings ''x'', ''y'' and ''z'' such that: | * Pumping lemma: A language '''L''' is regular if and only if there exists a positive integer ''m'' such that for any ''w'' ∈ '''L''' with |''w''| ≥ ''m'' there exist strings ''x'', ''y'' and ''z'' such that: | ||
** ''w'' = ''xyz'', | ** ''w'' = ''xyz'', | ||
| Line 11: | Line 12: | ||
** |''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)=== | ||
* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs | * Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs | ||