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]]
* 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
Line 11: Line 11:


===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]], a proper superset of RL's
* Recognized by nondeterministic pushdown automata
* Recognized by nondeterministic pushdown automata
** Deterministic pushdown automata cannot recognize all CFL's!
** Deterministic pushdown automata cannot recognize all CFL's!
Line 21: Line 21:
* LR(''n'') (Knuth, 1965):
* LR(''n'') (Knuth, 1965):
===Context-Sensitive Languages===
===Context-Sensitive Languages===
* Type 1 of the Chomsky Hierarchy, a proper superset of CFL's
* Type 1 of the [[Chomsky Hierarchy]], a proper superset of CFL's
* 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]], a proper superset of CSL's
* Recognized by Turing Machines
* Recognized by [[Turing Machines]]
===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])===
* Decided by [[Turing Machines]]


[[Category: CS GRE Prep]]
[[Category: CS GRE Prep]]

Revision as of 22:27, 9 October 2009

Formal Languages

Regular Languages (Class REG)

  • Type 3 of the Chomsky Hierarchy
  • 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 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, 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)

Recursive Languages (Class R)