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. Megnéztük egy kicsit még 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. és 3. feladatot. Megbeszéltük, hogy a 2.-t úgy kell, hogy elõször determinizálunk, aztán felcseréljuk az elfogadó és elutasító állapotokat, aztán ami kijön automata, ahhoz adunk reguláris kifejezést. A 4. feladat ötlete: mindkét kifejezéshez kell minimálautomata. Ha ezek azonosak, akkor a két nyelv ugyanaz, ha nem, akkor nem. A következõ óra elején megbeszéljük a hatost. A többi otthonra van. 5. A pumpálási lemmát elmondtam. Ezzel lehet a 7. és 8. feladatot megoldani. Formális nyelvek gyakorlat (4) 2000. október 4., szerda 1. Adjunk reguláris kifejezést az alábbi automatához! 2. Add meg reguláris kifejezéssel az alábbi automata által elfogadott nyelv komplementerét! ( $\Sigma = \{a,b\}$) 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! $$((a+b) b^* a)^* \quad \quad \mbox{\rm és} \quad \quad (a+b) (b+a(a+b))^* a + \epsilon$$ 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?