AG = (G,A,R) on korrektselt määratud, kui iga keele sõna x korral on tuletuspuus
kõigi atribuutide väärtused määratud.
Sõna x semantika on väärtus:
(X,k1,..,km) =
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, vasakule või jääda paigale. Kogu aeg on masinal mingi olek. Üks neist on lähteolek, lõppolekuid võib olla 0…n. Üleminekufunktisoon on nagu käsk: qa→rbD. Kui oled olekus q ja loed lindilt a, siis lähed olekusse r,
annaabi.ee 
