Context free languages
Often denoted as “CFL” or “CFG”.
Context free languages correspond to:
- Pushdown automata (PDA)
- Kleene algebra with least fixed-point operator (μ) ↗ or language equations (with solution under least fixed-point)
- Hence Brzozowski derivative (without intersection and negation)
- Type 2 Chomsky grammar
- A lot of parsers, like GLR: Generalised LR(k), GLL: Generalised LL
Closure properties
TODO
Decidability
TODO
Pumping lemma
TODO