-----------------------------
01. Lema o napihovanju za KNJ
-----------------------------
- dokaz, da nek jezik ni kontekstno neodvisen - primer

--------------------------------
02. Odločitvene lastnosti za KNJ
--------------------------------
- je nek KNJ prazen?
- članstvo (wϵL?)
	+ CYK algoritem - primer
- je nek KNJ neskončen?
- neodločljivi problemi
	+ sta dva KNJ enaka?
	+ sta dva KNJ disjunktna?

----------------------------
03. Lastnosti zaprtja za KNJ
----------------------------
- KNJ so zaprti za:
	+ unijo, stik, Kleene-ovo ovojnico
	+ zrcaljenje, homomorfizem, inverzni homomorfizem
	+ presek z RJ
- KNJ niso zaprti za:
	+ presek, razliko, komplement

--------------------
04. Turingovi stroji
--------------------
- zakodiramo vse kot celo število
	+ končno/neskončno, preštevnost, oštevilčenje
	+ več jezikov kot nizov --> diagonalizacija
- definicija TS
- trenutni opisi
- jezik TS
	+ sprejemanje v končnem stanju
	+ sprejemanje z ustavljanjem
	+ ekvivalenca obeh vrst sprejemanja
- rekurzivno preštevni in rekurzivni jeziki
- razširitve TS:
	+ več-sledni TS, spomin v stanju
	+ več-tračni TS
	+ nedeterministični TS
	+ pomnilnik naslov-vrednost (RAM)
- omejeni TS:
	+ TS s trakom, ki je neskončen le v eno smer
	+ skladovni avtomat z 2 skladoma

--------------------------------
05. Lastnosti zaprtja jezikov TS
--------------------------------
- rekurzivni jeziki so zaprti za:
	+ razliko, komplement
- rekurzivno preštevni jeziki so zaprti za:
	+ homomorfizem
- obe skupini jezikov sta zaprti za:
	+ unijo, stik, Kleene-ovo ovojnico
	+ zrcaljenje, presek, inverzni homomorfizem

----------------
06. Odločljivost
----------------
- TS kot binarni nizi
- Univerzalni Turingov stroj (UTM)
- neodločljivi problemi/jeziki:
	+ diagonalni jezik (L_d) --> ni rekurzivno prešteven
	+ univerzalni jezik (L_u) --> rekurzivno prešteven, a ne rekurziven
- Rice-ov teorem (L_p je neodločljiv za vsak p)
- Prevedba (Karp, Cook)
- TS kot pretvornik
- dokazovanje neodločljivosti jezikov (s prevedbami):
	+ L_p je neodločljiv (L_u --> L_p)
	+ (Modificiran) Post-ov Korespondenčni Problem ((M)PCP) je neodločljiv
	  (L_u --> MPCP --> PCP)
	+ problem dvoumnosti KNS je neodločljiv (PCP --> KNS dvoumnost)
	+ problem ekvivalence KNJ je neodločljiv
	  (DSA za komplement jezika, "L=Σ*?" je neodločljiv)
	+ problem regularnosti KNJ je neodločljiv