T: 1)lisame uue algsümboli S0 ja produktisooni S0 → S (nüüd ükski parem pool ei sisalda lähtesümbolit) 2) kaotame kõik A → ε. Kui T → Aa ja A → ε, siis kustutame A → ε ja lisame T → a (sama mis T → εa) 3) kaotame kõik A → B. Kui T → A ja A → a, siis asendame T → A kohe produktsiooniga T → a. 4) sobitame muud reeglid, kasutades abi-mitteterminaale. Nt S→aTb muudame S→AC, lisame A→a, C→TB, B→b. 10 KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm. Cocke-Kasami-Younge’i algoritmi abil saame teada, kas sõne kuulub KV keelde L. antud: KV grammatika Chomsky normaalkujul ja sõne w=w1…wn tulemus: accept, kui w selle grammatikaga keelde. Else, reject. tehakse püramiidikujuline tabel, mille alumisse ritta pannakse etteantud sõne kõik osad ja igasse tabeli lahtrisse kuidas neid kombinatsioone saada. Produktsiooni X → a korral pannakse “a saamise lahtrisse” X.
mitteterminaal vasakus pooles paremalt vasakule läbi käima. o asendan iga produktsiooni, milles paremal esimesel kohal suurem mitteterminaal hulga produktsioonidega, milles see mitteterminaal on vasakus pooles (ehk siis A>B>C korral ja C BD korral A CB asendan A BDB ) Iga keele jaoks leidub genereeriv grammatika Greibachi normaarkujul. 16. KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm. Cocke-Kasami-Youngeri algoritm: Chomsky normaalkujul oleva grammatika ning terminaalse stringi korral otsustab, kas sõna kuulub keelde või mitte. Ühendab kõikvõimalikud tuletuspuud tuletuspäramiidiks. Tabeli alumise astme laiuseks saab analüüsitava sõna pikkus. Tipulahtrisse peab tekkima stardisümbol. Vahepealsetesse lahtritesse kirjutatakse mitteterminaal parajasti siis, kui ... Algoritmi tulemusena tekib lahtrisse mitteterminaal A, kui grammatikas G on
annaabi.ee 
