Theory: Difference between revisions
No edit summary |
|||
| (5 intermediate revisions by the same user not shown) | |||
| 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 | ||
| Line 20: | Line 22: | ||
* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection | * The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection | ||
* Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input CFLs | * Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input CFLs | ||
====Efficiently-Parsed CFLs==== | ====Efficiently-Parsed CFLs (using ''n'' tokens of lookahead)==== | ||
* LL(''n'') (Lewis and Stearns, 1968): | * LL(''n'') (Lewis and Stearns, 1968): | ||
** Language equality is decidable for the ''simple grammars'', a subset of LL(1) | ** Language equality is decidable for the ''simple grammars'', a subset of LL(1) | ||
* LR(''n'') (Knuth, 1965): | * LR(''n'') (Knuth, 1965): | ||
* LALR(''n''): | * LALR(''n''): | ||
===Context-Sensitive Languages=== | ===Context-Sensitive Languages=== | ||
* Type 1 of the [[Chomsky Hierarchy]], and 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 | * 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 | ||
===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])=== | |||
* Decided by [[Turing Machines]] | |||
===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]], and 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 | * 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 <i>but not decided</i> by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt) | ||
== | |||
==Closures== | |||
{|class="wikitable borders" | |||
! class !! concat !! union !! intersection !! kleene !! setdiff !! complement | |||
|- | |||
| REG || Y || Y || Y || Y || Y || Y | |||
|- | |||
| CFL || Y || Y || n || Y || n || n | |||
|- | |||
| R || Y || Y || Y || Y || Y || Y | |||
|- | |||
| RE || Y || Y || Y || Y || n || n | |||
|- | |||
|} | |||
[[Category: CS GRE Prep]] | [[Category: CS GRE Prep]] | ||