DEF: KS grammatika on nelik G = (N,Σ,P,S), kus N on mitteterminaalide tähestik; Σ on terminaalide 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
8. Fraasistruktuuri grammatikad. Chomsky klassifikatsioon. Grammatika: Formaalne aparatuur keele ja tema fraasistruktuuri esitamiseks. Keel on teatud tähestiku = {a0, .., an} stringide alamhulk. L = {x | x kuulub *, P(x)} alamhulgaks kõigi stringide alamhulgale. Predikaat on semantika aluseks. Terminaalide tähestik = keeele tähestik. Mitteterminaalide tähestik N = hulk fraase tähistavaid metasümboleid Stringid tähestikus V = ühend N on lausevormid. Teisendusreegel e produktsioon kui lausevormide paar alfa -> beta. Generatiivne grammatika e grammatika: Nelik G = (,N,P,S0) - terminaalide tähestik N mitteterminaalide tähestik P produktisoonide hulk S0 stardisümbol Lausevormis vahetult tuletatav (vahetu tuletatavus kui binaarne relatsioon hulgal V*, tähistatakse =>G) lausevorm. Grammatika poolt genereeritav keel L(G) = {w | w kuulub * AND w on kaudselt tuletatav S0}. Grammatikate hierarhia: 0-tüüpi (L0) .
annaabi.ee 
