zkouska 24.6.

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
Uživatelský avatar
Andreas
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 18. 1. 2006 16:47
Typ studia: Informatika Bc.
Kontaktovat uživatele:

zkouska 24.6.

Příspěvek od Andreas »

Konecne se mi taky podarilo prolezt testem. Priklady z testu na ktere si vzpominam:
Byla tam definice automatu, ktera vypadala presne jako pro zasobnikovy, az na hvezdicku v prechodove funkci(vyskytuje se to casto!) delta: Q x X u{lambda} x Y -> PFIN(QxY) ... spravne je PFIN(QxY*)
a otazka byla: tento automat prijima prave jazyky: Odpovedi si bohuzel nepamatuju, ale neni tezke vymyslet spravnou odpoved(Y je konecna a na zasobnik si muzeme ukladat jen jedno pismeno, to lze nasimulovat i pres konecnou mnozinu stavu).

Otazka na vztah mnozin vsech bezprefixovych(A) a deterministickych(B) jazyku(ted presne nevim). Odpovedi byly:
A = B
A podmnozina B (spravne)
B podmnozina A
A /= B ( nerovna se) (!take spravne-tady jsem se nechal nachytat)

Uz tu nekde na foru je, ale znovu zopakuji: L* - {lambda} /= L+ jiz L totiz muze obsahovat lambdu

Pokud jsou dva jazyky ze stejne tridy Chomskeho hierarchie, pak:
a)jejich sjednoceni vzdy patri do stejne tridy
b)jejich sjednoceni vzdy patri do jine tridy
c)jejich prunik patri do stejne tridy
a jeste jedna.
Pokud se nepletu, tak neplati ani jedno tvrzeni a zaskrtnute nemelo byt nic.

Dalsi priklady, co si pamatuju, tak uz tu na foru jsou.

V druhe casti jsem dostal sestavit jednoduchy zasobnikovy automat, prijimajici prazdnym zasobnikem jazyk spravnych uzavorkovani. leva zavorka = 0, prava = 1. Priklad uz tu je s kompletnim zadanim.
Automat jsem napsal, vetsinu definic taky a prevod jsem mel jen z prijimani prazdnym zasobnikem na prijimani stavem.
Na ustni jsem si pockal cca 3 hodiny(sel jsem skoro posledni) a dost jsem se bal, ze tam mam par drobnych chybicek a napr. mi uplne chybela definice ZA. Obavy byly zbytecne, na ustni jsem tam jeste mohl neco opravit, co mi chybelo, tak mi dal dopsat, zeptal se na par veci k prevodu prijimani stavem => prij. zasobnikem a opacne(treba proc musi byt na zasobniku podlozka) a sel jsem velice prekvapen s jednickou domu:)(z testu pouhych 20 bodu)

Jinak po minulem neuspesnem pokusu a opetovnem ztroskotani na testu jsem dosel k panu docentovi na konzultaci prave toho testu a mam pocit, ze prave to mi pomohlo nakonec projit. Kdo s tim mate problemy, nebojte se za nim dojit.

//snad tu nepisu blbosti, nemam cas si to po sobe precist:)
New systems generate new problems:)
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: zkouska 24.6.

Příspěvek od lickra »

Pokud se nepletu, tak neplati ani jedno tvrzeni a zaskrtnute nemelo byt nic.
to se pletes!!!
Pro dva jazyky z Chomskeho h. plati ze jejich sjednoceni patri do stejne tridy.
DBKJ neni z chomskeho hierarchie!!
Potreba odpovidat na to co se pta!!!
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“