-------------------------
01. Pumping lemma for CFL
-------------------------
- prove that a language is not context-free - example

-------------------------------
02. Decision properties for CFL
-------------------------------
- is a CFL empty?
- membership (wϵL?)
	+ the CYK algorithm
- is a CFL infinite?
- non-decision properties
	+ are two CFLs the same?
	+ are two CFLs disjoint?

------------------------------
03. Closure properties for CFL
------------------------------
- CFLs closed under:
	+ union, concatenation, Kleene closure
	+ reversal, homomorphism, inverse homomorphism
	+ intersection with a RL
- CFLs not closed under:
	+ intersection, difference, complementation

-------------------
04. Turing machines
-------------------
- coding everything as integers
	+ finite/infinite, countability, enumeration
	+ more languages than strings --> diagonalisation
- TM definition
- instantaneous descriptions
- language of a TM
	+ accepting by final state
	+ accepting by halting
	+ equivalence of final state and halting acceptance
- recursively enumerable and recursive languages
- extensions of TMs:
	+ multi-track TM, caching in the state
	+ multi-tape TMs
	+ non-deterministic TMs
	+ name-value store machine (RAM)
- restricted TMs:
	+ semi-infinite tape TMs
	+ 2-stack/counter pushdown automata

------------------------------------------
05. Closure properties of languages of TMs
------------------------------------------
- recursive languages are closed under:
	+ difference, complementation
- recursively enumerable languages are closed under:
	+ homomorphism
- both language groups are closed under:
	+ union, concatenation, star
	+ reversal, intersection, inverse homomorphism

----------------
06. Decidability
----------------
- TMs as binary strings
- the Universal Turing machine (UTM)
- undecidable problems/languages:
	+ the diagonalisation language (L_d) --> not recursively enumerable
	+ the universal language (L_u) --> recursively enumerable, but not recursive
- Rice's Theorem (L_p is undecidable)
- Reduction (Karp, Cook)
- TM as a transducer
- proving undecidability of languages (by reduction):
	+ L_p is undecidable (L_u --> L_p)
	+ the (Modified) Post's Correspondence Problem ((M)PCP) is undecidable
	  (L_u --> MPCP --> PCP)
	+ the CFG ambiguity problem is undecidable (PCP --> CFG ambiguity)
	+ the CFL-eqivalence problem is undecidable
	  (DPDA for complement language, "=Σ*" is undecidable)
	+ the CFL-regularity problem is undecidable