Theory

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 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
• Nondeterminism (NFAs) adds no power to finite state automata (DFAs).

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)

• Type 0 of the Chomsky Hierarchy, a proper superset of CSL's
• 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