------------------------------- 01. Kontekstno neodvisni jeziki ------------------------------- - načini opisa KNJ (slovnice: KNS, KOS; skladovni avtomati; opisno - primer) - primernost posamezne predstavitve KNJ (edino DSA lahko "sprogramiramo") --------------- 02. Kaj je KNS? --------------- - matematična definicija - KNS, ki (ne) sprejemajo besede - izpeljave - stavčne oblike - jezik slovnice - Bachus-Naur-ova oblika - BNF notacija - skrajno leve (desne) izpeljave - drevesa izpeljav + pridelek + skrajno leve (desne) izpeljave - (ne)dvoumnost slovnic + LL(1) slovnice + inherentna dvoumnost nekaterih KNJ - "čiščenje" slovnice + ɛ-produkcije + enotne produkcije + spremenljivke, ki ne izpeljejo končnih besed + nedosegljive spremenljivke - Normalna oblika po Chomskem (CNF) -------------- 03. Kaj je SA? -------------- - matematična definicija - grafična predstavitev (ɛ-NKA + sklad) - SA - primer - trenutni opisi (ID) & "gre v" relacija - jezik SA + sprejemanje v končnem stanju L(P) + sprejemanje s praznim skladom N(P) + ekvivalenca L(P) in N(P) -- simulacije ----------------------------------- 04. Od ene predstavitve KNJ k drugi ----------------------------------- - KNS --> SA - SA --> KNS ------------------- 05. Več o slovnicah ------------------- - kontekstno odvisne slovnice (KOS) - prilastkovne KNS - RI --> KNS