Theory

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
• Pumping lemma: A language L is regular if and only if there exists a positive integer m such that for any w ∈ L with |w| ≥ m there exist strings x, y and z such that:
  • w = xyz,
  • |xy| ≤ m,
  • |y| ≥ 1, and
  • xyⁱz ∈ L 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)

• Decided by Turing Machines