Formális nyelvek vizsga 2001. május 29. A feladatok nem nehézségi sorrendben vannak. Az elsõ 5 példa 8-8 pontot ér, az utolsó példa (a) része 8 pont, a (b) része pedig 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 $\{a,b\}$ ábécé feletti szavakból áll, melyek legalább kétszer tartalmazzák a $bab$ részszót! Vigyázat: a két elõfordulás lehet átfedõ, tehát például a $babab$ szó is ilyen! A minimalitást is indokolni kell és az automata jóságát is! Bizonyítsd be, hogy nem reguláris az a nyelv, mely azon $2n$, $n\geq 0$ (tehát páros) hosszúságú $\{a,b\}$ feletti szavakból áll, melyeknek mind az elsõ $n$, mind a második $n$ karaktere között páros sok $a$ szerepel. Tehát jó szavak például: $bbaa$, $baaaba$, $bb$, $\epsilon$, rosszak például: $abb$, $aaba$. Adj veremautomatát az elõzõ feladatban leírt nyelvre! 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}BS\;\vert\;a$ $B\ensuremath{\rightarrow}SS\;\vert\;b$ Készíthetõ-e gyenge $LL(1)$ elemzõ az alábbi nyelvtanhoz? $S\ensuremath{\rightarrow}ABBA$ $A\ensuremath{\rightarrow}a\;\vert\;\epsilon$ $B\ensuremath{\rightarrow}b\;\vert\;\epsilon$ (a) Készíts $LR(1)$ elemzõt az $S\ensuremath{\rightarrow}aSS\;\vert\;b$ nyelvtanhoz! (b) Elemezd az (a) pontban kapott elemzõvel az $ababb$ szót!