Check out my first novel, midnight's simulacra!

Theory: Difference between revisions

From dankwiki
No edit summary
No edit summary
Line 1: Line 1:
==Formal Languages==
==Formal Languages==
===Regular Languages===
===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
* Recognized by finite state machines

Revision as of 09:44, 7 September 2009

Formal Languages

Regular Languages (Class REG)

  • Type 3 of the Chomsky Hierarchy
  • Recognized by finite state machines
  • Closed under union, concatenation, Kleene, intersection, difference, complement, reverse

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
  • LL(n):
  • LR(n):

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