Check out my first novel, midnight's simulacra!

Theory

From dankwiki
Revision as of 09:44, 7 September 2009 by Dank (talk | contribs)

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