Theory

Formal Languages

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 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

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

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):

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

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)