Check out my first novel, midnight's simulacra!

Theory

From dankwiki

Formal Languages

Regular Languages (Class REG)

  • Type 3 of the Chomsky Hierarchy (rewrite rules: A→a and A→aB)
  • 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)