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) .. ei lisakitsendusi
Tuletus koosneb 2 tuletussammudest. Üks tuletussamm on mingi konkreetse väite tuletamine eelduste või varem saadud vahetulemuste põhjal. Tuletusreeglid näitavad, mida saab mingi kujuga lausena esitatud väitest (oletusest) või väidetest selles tuletussammus järeldada, milline on sammu tulem. Tuletusreegleid ei tohi kasutada asenduste tegemiseks tuletussammu eeldustes või tulemites, selleks saab kasutada teisendusreegleid ehk asendusreegleid. Teisendusreegel lubab mingi sümboli või valemi asendada teise sümboli või valemiga. Asendusi saab teha ka valemi sees. Nt koolialgebra valemites võib valemi (a + a) asendada sümboliga 2a, lausearvutuses võib valemis (¬A ˅ B) & (A → ¬A ˅ B) iga disjunktsiooni kujul ¬A ˅ B asendada implikatsiooniga A → B (vt lausearvutuse teisendusreeglite tabelit). Teisendusreeglit saab vaadelda kui kehtivat arutlust, millel on üks eeldus ja üks lõppjäreldus, kusjuures reegel
tuletussammudest. Üks tuletussamm on mingi konkreetse väite tuletamine eelduste või varem saadud vahetulemuste põhjal. Tuletusreeglid näitavad, mida saab mingi kujuga lausena esitatud väitest (oletusest) või väidetest selles tuletussammus järeldada, milline on sammu tulem. Tuletusreegleid ei tohi kasutada asenduste tegemiseks tuletussammu eeldustes või tulemites, selleks saab kasutada teisendusreegleid ehk asendusreegleid. Teisendusreegel lubab mingi sümboli või valemi asendada teise sümboli või valemiga. Asendusi saab teha ka valemi sees. Nt koolialgebra valemites võib valemi (a + a) asendada sümboliga 2a, lausearvutuses võib valemis (¬A B) & (A ¬A B) iga disjunktsiooni kujul ¬A B asendada implikatsiooniga A B (vt lausearvutuse teisendusreeglite tabelit). Teisendusreeglit saab vaadelda kui kehtivat arutlust, millel on üks eeldus ja üks lõppjäreldus, kusjuures reegel
annaabi.ee 
