Check out my first novel, midnight's simulacra!
Theory: Difference between revisions
From dankwiki
| Line 11: | Line 11: | ||
** |''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 21: | Line 20: | ||
* 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 input CFLs | * Universality, language equality, language inclusion, and regularity are all undecidable given input CFLs | ||
====Efficiently-Parsed CFLs==== | ====Efficiently-Parsed CFLs==== | ||
* LL(''n'') (Lewis and Stearns, 1968): | * LL(''n'') (Lewis and Stearns, 1968): | ||
| Line 27: | Line 25: | ||
* 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 | ||
| Line 37: | Line 33: | ||
* 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 by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt) | ||
===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])=== | ===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])=== | ||
* Decided by [[Turing Machines]] | * Decided by [[Turing Machines]] | ||
[[Category: CS GRE Prep]] | [[Category: CS GRE Prep]] | ||
Revision as of 23:08, 9 October 2009
Formal Languages
Regular Languages (Class REG)
- 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).
- 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, 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 (NPDAs)
- Deterministic pushdown automata (DPDAs) cannot recognize all CFLs (only the DCFLs)!
- 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
- Universality, language equality, language inclusion, and regularity are all undecidable given input CFLs
Efficiently-Parsed CFLs
- LL(n) (Lewis and Stearns, 1968):
- Language equality is decidable for the simple grammars, a subset of LL(1)
- LR(n) (Knuth, 1965):
- LALR(n):
Context-Sensitive Languages
- 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
Recursively-Enumerable Languages (Class RE)
- 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)
Recursive Languages (Class R)
- Decided by Turing Machines
