Rekursiooni ja keerukusteooria eksami konspekt
tähestik (neil pole ühisosa), P ⊆ (N∪Σ)*N(N∪Σ)*×(N∪Σ)* on produktsioonide lõplik hulk, S ∈ N on
lähtesümbol ja iga α → β korral on β pikkus suurem kui α pikkus, v.a produktsioon S → ε.
Chomsky keelte klassifikatisioon:
• kitsenduseta fraasistruktuuri keeled: α → β, kus α ja β on mis tahes lausevormid tähestikus V = Σ∪N;
• KS keeled: α → β , kus α sisaldab vähemalt üht mitteterminali ja |α| <= |β|, v.a. S → ε;
• KV keeled: A→β;
• regulaarsed keeled: A→a ja A→aB.
Turingi masina keeled on kõik kitsenduseta fraasistruktuuri keeled. On ka mitte-TM keeli.
16 Turingi masin ja registermasin. Lahenduvad ja rekursiivselt loenduvad hulgad.
Turingi masina sisendiks on mõlemas suunas lõpmatu lint, millelt saab korraga lugeda 1 sümboli. See
kirjutatakse ka üle kas siis selle sama v mõne muu sümboliga. Liikuda saab igal taktil kas 1 koht paremale,
annaabi.ee 
