Check out my first novel, midnight's simulacra!
Theory: Difference between revisions
From dankwiki
| 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) | ||
* 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 | ||
Revision as of 22:49, 9 October 2009
Formal Languages
Regular Languages (Class REG)
- Type 3 of the Chomsky Hierarchy (rewrite rules: A→a and A→aB)
- Recognized by finite state machines. Equivalent to DSPACE(1).
- Closed under union, concatenation, Kleene, intersection, difference, complement, reverse, right-quotient, homomorphism
- 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,
- |xy| ≤ m,
- |y| ≥ 1, and
- xyiz ∈ L for all i ≥ 0
Context-Free Languages (CFLs) / Grammars (CFGs)
- Type 2 of the Chomsky Hierarchy, a proper superset of RL's
- Recognized by nondeterministic pushdown automata
- Deterministic pushdown automata cannot recognize all CFL's!
- Closed under union, concatenation, Kleene, reverse
- Not closed under complement or difference
- The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection
Efficiently-Parsed CFLs
- LL(n) (Lewis and Stearns, 1968):
- LR(n) (Knuth, 1965):
Context-Sensitive Languages
- Type 1 of the Chomsky Hierarchy, a proper superset of CFL's
- Recognized by linear bounded automata
Recursively-Enumerable Languages (Class RE)
- Type 0 of the Chomsky Hierarchy, a proper superset of CSL's
- Recognized by Turing Machines (ie, any 'yes' answer can be verified, but 'no' cases might not halt)
Recursive Languages (Class R)
- Decided by Turing Machines
