Formális nyelvek vizsga 2001. június 19. A feladatok nem nehézségi sorrendben vannak. Az elsõ 5 példa 8-8 pontot ér, az utolsó példa (a) része 6 pont, a (b) és (c) rész pedig 2-2. Így összesen 50 pontot lehet elérni, a vizsga 20 ponttól sikeres. A MEGOLDÁSOKAT INDOKOLD MEG! Jó munkát! Megoldás ps-ben Adj minimálautomatát ahhoz a nyelvhez, mely azon $\{0,1\}$ ábécé feletti szavakból áll, melyekben minden páros hosszú teljes homogén 0-sorozatot páros hosszú teljes homogén 1-sorozat követ és minden páratlan hosszú teljes homogén 0-sorozatot páratlan hosszú teljes homogén 1-sorozat követ. A minimalitást is indokolni kell és az automata jóságát is! Adj reguláris nyelvtant az alábbi nyelvhez! $$\{0^a1^b0^c\;\vert\;b=2, a+c \;\;p\acute aratlan\}$$ Magyarázd el, hogy a nyelvtanod hogyan mûködik és miért az adott nyelvet generálja! Adj veremautomatát ahhoz az {a,b} feletti nyelvhez, mely azon szavakból áll, melyek hossza páratlan és legalább 3, s amelyekben az elsõ betû megegyezik a középsõ betûvel és az utolsó betûvel is. Jelöld, hogy az automata hogyan fogad el és lásd el magyarázatokkal az automata szabályait (melyik mit csinál és miért)! Adj az alábbi nyelvtannal ekvivalens (ugyanazt a nyelvet generáló) Greibach normál alakú nyelvtant: $S\ensuremath{\rightarrow}SSa\;\vert\;b$ Bizonyítsd be, hogy nem elemezhetõ gyenge precedencia elemzõvel az alábbi nyelvtan! $S\ensuremath{\rightarrow}a\;\vert\;(S)\;\vert\;i(L)$, $L\ensuremath{\rightarrow}L-S\;\vert\;S$ (a) Készíts gyenge $LL(k)$ elemzõt minél kisebb $k$-val az $S\ensuremath{\rightarrow}aaSbb\;\vert\;a\;\vert\;\epsilon$ nyelvtanhoz! (b) Van-e a (a) pontban kapott $k$-val erõs $LL(k)$ elemzõ a nyelvtanhoz? (b) Elemezd az (a) pontban kapott elemzõvel az $aaaaabbb$ szót!