Check out my first novel, midnight's simulacra!

Theory: Difference between revisions

From dankwiki
 
(10 intermediate revisions by the same user not shown)
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]] (rewrite rules: A→a and A→aB)
* 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 [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 9: 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
* Nondeterminism (NFAs) adds no power to finite state automata (DFAs).


===Context-Free Languages (CFLs) / Grammars (CFGs)===
===Context-Free Languages (CFLs) / Grammars (CFGs)===
* Type 2 of the [[Chomsky Hierarchy]], a proper superset of RL's
* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs
* Recognized by nondeterministic pushdown automata
* Rewrite rule: A→γ, where A is a non-terminal, and γ is a string of terminals and non-terminals
** Deterministic pushdown automata cannot recognize all CFL's!
* Recognized by nondeterministic pushdown automata (NPDAs)
** Deterministic pushdown automata (DPDAs) cannot recognize all CFLs (only the DCFLs)!
* Closed under union, concatenation, Kleene, reverse
* Closed under union, concatenation, Kleene, reverse
* Not closed under complement or difference
* Not closed under complement or difference
* 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
====Efficiently-Parsed CFLs====
* Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input 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)
* LR(''n'') (Knuth, 1965):
* LR(''n'') (Knuth, 1965):
* LALR(''n''):
===Context-Sensitive Languages===
===Context-Sensitive Languages===
* Type 1 of the [[Chomsky Hierarchy]], a proper superset of CFL's
* 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
* Recognized by linear bounded automata
===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]], a proper superset of CSL's
* 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)
* 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]]

Latest revision as of 02:19, 4 April 2013

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, 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 wL with |w| ≥ m there exist strings x, y and z such that:
    • w = xyz,
    • |xy| ≤ m,
    • |y| ≥ 1, and
    • xyizL 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 arbitrary input CFLs

Efficiently-Parsed CFLs (using n tokens of lookahead)

  • 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)