Theory

From dankwiki
Jump to navigation Jump to search

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)