Sziasztok!

0. A legérdekesebb: a jövő héten kis zh lesz. Anyaga minden, amit eddig tanultunk a véges automatákkal, reguláris nyelvekkel, reguláris kifejezésekkel kapcsolatban. Pontosabban: ezt mindet kell tudni.

1. Ezentúl minden héten lesz feladatmegoldó konzultáció. Itt csak olyan feladatok lesznek, amiket órán feladtam, de nem beszéltünk meg, vagy amik a gyakorlók között szerepelnek.

Helye és ideje: csütörtök, reggel fél kilenc, az I.B. 134-ben. Ez a tanszéken van (SZIT), ahogy bejöttök az ajtón, rögtön szemben. Halkan közlekedjetek, mert a többi ember ott dolgozni szeretne.

2. Van egy nehéz feladatokból álló feladatsor az érdeklődőknek. Ezeknek a megoldásait lapon lehet beadni.

3. Megbeszéltük a 2VA-s múlt órai 4. feladatot, az 5. feladatnál meg trükköket mutattam, hogy hogyan lehet elkerülni a falak számolását. Aki nem volt, az kérdezze meg valakitől, hogy hogyan. Beadandó házi : (külön lapon) a múltkori sor 6. és 7. feladata. Javaslat: a hatost a trükkös megoldással érdemes, a hetest falakkal lehet megcsinálni.

4. A mai feladatsorból megcsináltuk az 1., 2., 3. feladatot. A következő óra elején megbeszéljük a hatost.

5. A pumpálási lemmát elmondtam. Ezzel lehet a 7. és 8. feladatot megoldani.

Formális nyelvek gyakorlat (4)

2000. október 2., hétfő

1. Adjunk reguláris kifejezést az alábbi automatához!

\includegraphics{r8.eps}

2. Add meg reguláris kifejezéssel az alábbi automata által elfogadott nyelv komplementerét! ( $\Sigma = \{a,b\}$)


\includegraphics{minta.eps}

3. Adj meg egy olyan (nemdeterminisztikus) véges automatát, amelynek nyelve az $(11+0)^* (00+1)^*$ reguláris kifejezéssel írható le.

4. Döntsük el, hogy az alábbi két reguláris kifejezés által leírt nyelv azonos-e!

\begin{displaymath}((a+b) b^* a)^* \quad \quad \mbox{\rm és} \quad \quad
(a+b) (b+a(a+b))^* a + \epsilon \end{displaymath}


5. Legyen $\Sigma=\{a,b,c\}$, továbbá $L_1 = \{w: \vert w\vert _a \mbox{ páratlan és } \vert w\vert _b \mbox{ páros}\}$ és $L_2$ álljon azokból az $a$-val kezdődő, $c$-vel végződő szavakból, amelyekben a három karakter ciklikusan követi egymást (azaz $a$ nem állhat közvetlenül $b$ után, $b$ nem állhat közvetlenül $c$ után és $c$ nem állhat közvetlenül $a$ után). Szerkesszen az $L_1 \cap L_2$ nyelvre minimálautomatát!

6. Az $L$ nyelvbe tartozzanak azok a szavak, melyekben van páratlan teljes homogén részsorozat. Szerkesszen minimálautomatát az alábbi nyelvekre: $L$, $L^2$, $L\cap L^2$, $L^*$! Az első és az utolsó nyelvet adja meg reguláris kifejezéssel is! ( $\Sigma = \{a,b\}$)

7. Reguláris-e az $\{\; a^mb^n\;\vert\; m\leq n\leq 2m\;\}$ nyelv?

8. Reguláris-e az $ \{a^ib^j\;\vert\; i>j\}$ nyelv?