Minimax (otsing mängupuust)- vaheldumisi maksimeerid ja minimeerid seisu. Masin teeb enda jaoks parima käigu, inimene teeb masin jaoks halvima käigu. Alpha-beta pruning Standardsele minimax mängupuule rakendades tagastab see sama käigu, mille tagastaks minimaxi algoritm, aga kärbib välja harud, mis lõplikku otsust kuidagi ei mõjuta. Alfa-beeta kärpimist on võimalik rakendada mistahes sügavusega puudele ning sageli on lehtede asemel võimalik kärpida terveid alampuid. Algoritmi üldine põhimõte on järgmine: Võtame vaatluse alla mängupuu tipu n. Kui mängijal on võimalik teha parem valik mistahes tipule n eelnevas tipus, siis tipuni n tegelikus mängus ei jõutagi. Seega, kui oleme tipu n kohta piisavalt infot kogunud (läbi vaadates osad tema järglastest), et sellele otsusele jõuda, võime n’i mängupuust kärpida. Alfa-beeta kärpimine on oma nime saanud kahelt parameetrilt, mis seavad piirid puuharudes esinevatele väärtustele.
Nii tagame, et (w,C0) * (e,Ck) mis tähendab, et automaat aktsepteerib keele mis omakorda tähendab, et keel on regulaarne. 13. KV-keelte süntaksi- ja tuletuspuud. Süntaksipuu: Iga järjestatud puu T = (A,R), mille tippude märgendus on antud kujutusega f, on esitatav termina: · kui tipp a on terminaalne tipp, siis märgend M = f(a) on term · kui tipp a on mitteterminaalne tipp märgendiga M = f(a), mille vahetuid alampuid vasakult paremale tähistavad termid t1 .. tn, siis avaldis M(t1,..,tn) on term, mis tähistab puu T alampuud juurega a Idee poolest sama on lrep(T) asendame lihtsalt tipud neile vastavate märgenditega. Puu kroon Kr(T) = string terminaalsete tippude märgenditest vasakult paremale kirjutades. Puu T1 terminaalse tipu A asendamine puuga T2 tähistatakse t = T1{A/T2} Märgendatud järjestatud elementaarpuid saab esitada kontekstivabade grammatikate produktsioonide esitamiseks.
annaabi.ee 
