Vajad kellegagi rääkida?
Küsi julgelt abi LasteAbi
✍🏽 Avalikusta oma sahtlis olevad luuletused! Luuletus.ee Sulge
Add link

"greibachi normaalkuju" - 2 õppematerjali

24
pdf

Rekursiooni ja keerukusteooria eksami konspekt

KV grammatikat realiseeriv pinuautomaat. Pinuautomaat on lõplik automaat koos magasinmäluga. Magasini saab laadida sümboleid, see on lõpmatu DEF: Lõplik pinuautomaat on struktuur M = (Q, Σ(sisendid), Γ(magasin), δ, Q0, F) δ :Q×Σε×Γε →P(Q×Γε) (hetkeolek x sisend x magasinist loetu = olek x magasini pandu Automaat aktsepteerib sõne, kui ta alustab lähteolekust ja tühja magasiniga ning jõuab aktsept. olekusse. a,b → c (sisend, magasinist loetu = magasini pandu) ε - sisendist v magasinist ei loeta v ei kirjutata sinna Teoreem: Iga KV keel on aktsepteeritav mingi magasinmäluga automaadi abil. nt {0n1n | n>0 } vt üleval. Lõpliku magasinmäluga automaadi poolt aktsepteeritav keel on kontekstivaba. KV keelte hulk ongi see hulk keeli, mida pinuautomaadid aktsepteerivad. 12 Ühe olekuga pinuautomaatide ja Greibachi mõttes normaliseeritud KV-grammatikate ekvivalentsus. Teoreem: Iga pinuautomaadi M jaoks leidub ühe olekuga M′, nii et nad aktsepteerivad samu keeli. T: teeme palindroome (aiassadassaia) aktsepteeriva automaadi, kogu olekute loogika on asendatud magasini panemise ja sealt võtmise loogikaga. Teoreem: Ühe olekuga pinuautomaadi M jaoks leidub KV grammatika G, nii et L(M)=L(G). DEF: KV grammatika on Greibachi normaalkujul , kui tema produktsioonid on kujul A→aA1A2…An või A→a (muu on tühi sõne) või kujul S → ε, kui keelde L (G) peab kuuluma ka tühi sõne. Iga KV grammatika on teisendatav Greibachi normaalkujule. T: 1) grammatika peab olema Chomsky nk-l. 
 2) mitteterminaalid nimetatakse ümber A1-ks, A2-ks jne. 3) produktsioonid asendatakse kujule aA1A2A3… Regulaarsete keelte hulk on KV keelte pärisosahulk. Vaatame kasvõi pumpamise lemmasid: uvjw on lihtsalt uvjwxjy erijuht ehk uvjwjxjy= u(vwx)jy. 13 Taandatu...

Informaatika - Tallinna Tehnikaülikool
78 allalaadimist
37
doc

Teoreetilibe informaatika kordamisküsimused

Hulkade spetsifitseerimine, tehted hulkadega, hulgateooria paradoksid. Hulk: Korteezh ­ järjestatud lõplik hulk. Hulk ­ mingi arv elemente, mille vahel on leitav seos ­ klassifitseeritud elementide kogum. Hulk ­ samalaadsete objektide järjestamata kogum. Hulga esitamine: elementide loeteluna A = {2;3;4} predikaadi abil A = {x | P(x)} Tühihulk on iga hulga osahulk. Iga hulk on iseenda osahulk. Hulga boleaan ­ kõigi osahulkade hulk. H boleaan on 2H. 2H = {x | x on osahulgaks H-le}. Boleaani võimsus |2H| = 2|H| Tühja hulga boleaani võimsus on 1. Tehted: Hulkade võrdsus = A on B osahulk AND B on A osahulk. Ekvivalentsiseose definitsioon ((A => B) && (B => A)) ­ hulgas sisaldavad samu elemente. Hulga osahulk ­ võib võrduda hulgaga. Hulga pärisosahulk ­ ei või võrduda. Hulkade ühend ­ C = {x...

Teoreetiline informaatika - Tallinna Tehnikaülikool
92 allalaadimist


Registreeri ja saadame uutele kasutajatele
faili e-mailile TASUTA

Konto olemas? Logi sisse

Sellel veebilehel kasutatakse küpsiseid. Kasutamist jätkates nõustute küpsiste ja veebilehe üldtingimustega Nõustun