Rekursiooni ja keerukusteooria eksami konspekt
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.
Esimeses reas vaadatakse, kuidas saada 1 täht, teises reas, kuidas saada 2 tähte jne
Nt kolme tähe w1w2w3 saamiseks on meil kaks võimalust: w1-w2w3, w1w2-w3
Nelja tähe w1w2w3w4 saamiseks on meil 3 võimalust: w1-w2w3w4, w1w2-w3w4, w1w2w3-w4.
1) iga w=ε kohta vaata, kui S→ε on reegel, siis accept. Else, reject.
2) iga A kohta vaata, kui A→wi on reegel, siis pane A tabelisse kohale (i,i)
3) vaadatakse, kuidas saada kõigi tähtede kombinatsioonid.
4) kui tabelis kõige kõrgemale (1,n) on tekkinud S, siis accept. Else, reject.
w1w2w3w4w5w6
annaabi.ee 
