Formális nyelvek vizsga 2001. június 12. 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 pont. Így összesen 50 pontot lehet elérni, a vizsga 20 ponttól sikeres. A MEGOLDÁSOKAT INDOKOLD MEG! Jó munkát! A feladatsor ps-ben, itt látszik az ábra is Megoldás ps-ben Adj minimálautomatát az alábbi véges automata által elfogadott nyelvhez! Adott 37 reguláris nyelv az $\{a,b\}$ ábécé felett. Igaz-e, hogy az alábbi L nyelv mindenképp reguláris? L-ben azon szavak vannak benne, melyek legalább 19 nyelvbe beletartoznak. Adj minél egyszerûbb osztályú nyelvtant az alábbi nyelvhez! $$L=\{a^nb^{2m}a^{n}\;\vert\;n,m\geq 1\}$$ A feladat része annak megmutatása is, hogy egyszerûbb nyelvtannal a nyelv nem generálható! Adj jellemzõ nyelvtant az alábbi fordításhoz: $$\mathcal{T}=\{(w,ww^{-1})\;\vert\;w\in {\{a,b\}}^*\}$$ Ha $w=x_1\ldots x_n$, akkor $w^{-1}=x_n\ldots x_1$, azaz $w^{-1}$ a $w$ szó tükrözésével, visszafele való leírásával kapható. A fordítást tehát olyan szópárok alkotják, melyek második tagja úgy áll elõ. hogy az elsõ tag után írjuk az elsõ tag tükörképét. Adj az alábbi nyelvtannal ekvivalens (ugyanazt a nyelvet generáló) jólfésült, Chomsky normál alakú nyelvtant: $S\ensuremath{\rightarrow}A\;\vert\;C$, $A\ensuremath{\rightarrow}aB\;\vert\;bS\;\vert\;b$, $B\ensuremath{\rightarrow}AB\;\vert\;Ba$, $C\ensuremath{\rightarrow}AS\;\vert\;b$ (a) Készíts gyenge $LL(k)$ elemzõt minél kisebb $k$-val az $S\ensuremath{\rightarrow}AB$, $A\ensuremath{\rightarrow}aAb\;\vert\;\epsilon$, $B\ensuremath{\rightarrow}bBc\;\vert\;\epsilon$ nyelvtanhoz! (b) Lehet-e erõs $LL(k)$ elemzõt csinálni a fenti nyelvtanhoz, az (a) pontban kapott $k$ értékkel? (c) Elemezd az (a) pontban kapott elemzõvel az $abbc$ szót!