Zkouška 10.6.2009 Barták

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).
cermi
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 31. 1. 2008 18:44
Typ studia: Informatika Bc.

Zkouška 10.6.2009 Barták

Příspěvek od cermi »

Zdarek, tak jsem se konečně vrátil ze zkoušky. Ranní zaškrtávací test dopadl celkem dobře, vyhodil jen 2 lidi. Dost otázek byla už známá z dřívějška, ale POZOR: doc. Barták dělá to, že vezme klasickou otázku a např v jedné z odpovědí změní index nebo jinou "drobnost", čímž to celé obrátí ... takže je potřeba to číst celé a podrobně a neříct si "jo, tuhle jsem dělal včera večer, to si ještě pamatuju, to je A a B".

Jinak u příkladů tam bylo hodně klasických, ale já jsem měl něco, co jsem nikde neviděl , takové pumping lemma pro lineární jazyky (+ještě pár věci o lineárních jazycích chtěl napsat):
L je lin. jazyk, pak ∃n takže pro z z Lka, |z|>=n platí že jde napsat z=uvwxy, tž vx!=λ, |uvxy|<=n, (možná ještě něco) a že jde pumpovat tj. ∀i>=0 uviwxiy je taky z L.
Snad jsem to nepopletl. Dokazoval jsem to podobně jako pumping lemma pro BKJ, takže si udělat derivační strom, uvědomit si, jak vypadá, stanovit n a dokázat ty 3 věci.
Těžké to asi nebylo, ale měl jsem tam 1 věc, kterou jsem nedokázal úplně, ale řekl, že 2ku mi dá rovnou, na 1ku bych to musel ještě doopravit, ale po několikahodinovém čekáni na chodbě jsem s díkem vzal 2ku a šel domů.

Pár lidí tam ale dusil snad hodinu nebo dvě na nějakých příkladech, takže zkouška až taková pohodička není :)
Čermi
Obrázek
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“