"klassifikatisioon" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt


 KS keeltel on erinevad produktsioonid cB →… ja bB →… sest muutumine sõltub, kas B ees on b või c. DEF: KS grammatika on nelik G = (N,Σ,P,S), kus N on mitteterminaalide tähestik; Σ on terminaalide tähestik (neil pole ühisosa), P ⊆ (N∪Σ)*N(N∪Σ)*×(N∪Σ)* on produktsioonide lõplik hulk, S ∈ N on lähtesümbol ja iga α → β korral on β pikkus suurem kui α pikkus, v.a produktsioon S → ε. Chomsky keelte klassifikatisioon: • kitsenduseta fraasistruktuuri keeled: α → β, kus α ja β on mis tahes lausevormid tähestikus V = Σ∪N; • KS keeled: α → β , kus α sisaldab vähemalt üht mitteterminali ja |α| <= |β|, v.a. S → ε; • KV keeled: A→β; • regulaarsed keeled: A→a ja A→aB. Turingi masina keeled on kõik kitsenduseta fraasistruktuuri keeled. On ka mitte-TM keeli. 16 Turingi masin ja registermasin. Lahenduvad ja rekursiivselt loenduvad hulgad.