Gyakorló feladatok formális nyelvekbõl 4. gyakorlat 1. Ehhez a nyelvtanhoz kell reguláris kifejezés! $S\ensuremath{\rightarrow}1A\vertB$, $A\ensuremath{\rightarrow}0A\vert 1A\vert 1$, $B\ensuremath{\rightarrow}0B\vert 1B\vert$. 2. Add meg reguláris kifejezéssel azt a nyelvet amelyik a $\{0,1\}^*$ azon szavaiból áll, amikben nem fordul elõ az 110 részszó! 3. Adott az alábbi három reguláris nyelv: ${(b^*ab^*a)}^*b^*$ $a^*b{(a^*ba^*b)}^*a^*$ ${(a+b)}^*a$ Legyen az $L$ nyelv azon szavak halmaza, amelyek a fenti három nyelv közül legalább kettônek mondatai! Adja meg az $L$-t elfogadó minimálautomatát! 4. Adott két nyelv az alábbi két egyenletrendszerrel. Készítse el a két nyelv metszetét felismerõ minimálautomatát! $S_1=aS_1+b(A+\epsilon)$ $S_2=aS_2+b(B+\epsilon)$ $A=bS_1+a(A+\epsilon)$ $B=S_2+b(B+\epsilon)$ 5. Adjunk determinisztikus véges automatát az alábbi nyelvhez: $L=\{{(1111)}^+w\;\vert\;w\in{\{a,b\}}^*\}$ 6. Legyen $\Sigma=\{a,b,c\}$ és $L = \{w: \vert w\vert _a + \vert w\vert _b \mbox{ páros és } \vert w\vert _b + \vert w\vert _c \mbox{ páratlan} \}$. Készítsünk minimálautomatát $L$-re, $L^2$-re és $L^*$-ra! 7. Az $L$ nyelv azon ${\{a,b\}}^*$ feletti szavakból áll, melyekben páratlan sok teljes homogén b-sorozat van. (i) Készítsen minimálautomatát az $L^2\cap L$ nyelvre! (ii) Adja meg a metszet nyelvet reguláris kifejezéssel! 8. Reguláris-e a $\{0^n1^m0^{n+m}\vert n, m\geq 1\}$ nyelv? 9. Igazoljuk, hogy az $\{0^{n!}\;\vert\; n\geq 0\}$ nyelv nem reguláris! 10. Az $L$ nyelv ábécéje a $\{0,1\}$. A nyelvbe azok a szavak tartoznak, melyekben ${\vert w\vert}_0={\vert w\vert}_1$ és amelyek minden prefixében $\vert{\vert w\vert}_0-{\vert w\vert}_1\vert\leq 1$. (i) Írjuk le reguláris kifejezéssel a fenti nyelvet! (ii) Adjunk a nyelvhez determinisztikus véges automatát! 11. Adott az alábbi $CF$ nyelvtan: $$\begin{eqnarray*} S& \ensuremath{\rightarrow}& 00S\;\vert\;RP\;\vert\;QT\\ P&\e... ...emath{\rightarrow}&11 \\ T & \ensuremath{\rightarrow}&\epsilon \end{eqnarray*}$$ (i) Adja meg a nyelvet reguláris kifejezésként! (ii) Készítsen hozzá harmadosztályú nyelvtant! (iii) Adja meg a nyelvet elfogadó minimálautomatát!