"mitteterminaalne" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

korral xa ja ya. Automaati lisame iga oleku Ci ja iga terminaali a jaoks kaare olekusse Cj. 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}