# Theory

From dankwiki

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

- Derivation with respect to
- 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*∈^{i}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)

- Language equality is decidable for the
- 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