Check out my first novel, midnight's simulacra!
Theory
From dankwiki
Formal Languages
Regular Languages (Class REG)
- Type 3 of the Chomsky Hierarchy
- Recognized by finite state machines. Equivalent to DSPACE(1).
- Closed under union, concatenation, Kleene, intersection, difference, complement, reverse
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
