Sziasztok! A mai óra anyaga: véges automaták (ilyet adni nyelvhez), determinizálás (determinisztikus automatát adni, meglevõt determinizálni, beleértve az epszilon-átmeneteket is), automatát reguláris nyelvtanná alakítani és visssza. Ezen utóbbihoz Varró Dani oldalain van jó kis segédanyag . Minden feladatot megoldottunk, kivéve a 3. ez házi, a 6., ez kimaradt és a 10. Ez utóbbit lapon lehet beadni. Formális nyelvek gyakorlat (2) 2000. szeptember 18., hétfõ 1. Adjunk determinisztikus véges automatát az alábbi nyelvhez: $L=\{w\in {\{a,b\}}^*\;\vert\;{\vert w\vert}_a$ osztható hárommal, |w|b osztható kettõvel$\}$. 2. Adjunk véges automatát (a) az üres nyelvre, azaz $L=\emptyset$, (b) a csak az $\epsilon$-t tartalmazó nyelvre, azaz $L=\{\epsilon\}$. 3. Készíts olyan véges automatát, amely a tizedestört alakban felírt racionális számokat fogadja el. Pontosabban az elfogadandó szám vagy tizedespont nélküli egész szám (pl. 123), vagy tartalmaz tizedespontot. Az utóbbi esetben azt is el kell fogadni, ha az egészrész vagy a törtrész hiányzik, de persze legfeljebb az egyik hiányozhat (pl. helyes az 123.456 vagy az 123. vagy a .456 is, de nem fogadható el ha a bemenet csak egyetlen pontból áll.). Megköveteljük továbbá azt is, hogy az egészrész ne kezdõdjön felesleges 0-kal (de pl. a 0.456 helyes). 4. Mutassuk meg, hogy (a) tetszõleges VA-t teljesen specifikálttá tehetünk (b) tetszõleges véges automatát át lehet úgy alakítani, hogy csak egy végállapota legyen (c) egy több kezdõállapottal rendelkezõ VA-t normális, azaz egy kezdõállapotossá lehet alakítani 5. Tegyük determinisztikussá az alábbi automatát!! 6. Adjunk determinisztikus véges automatát a következõ nyelvre: $L=\{w\in {\{0,1\}}^*\;\vert\;$ létezik két 0 w-ben, melyek között néggyel osztható számú egyes áll$\}$. 7. Determinizálni kell ezt: 8. Adjunk (jobb- és bal-)reguláris nyelvtant az 5. feladat automatájához! 9. Adjunk reguláris nyelvtant az (a+b)*aba(a+b)* nyelvhez, majd a nyelvtanból szerkesszünk automatát! 10. A 2. része nehéz (a) Adjunk n+1 állapotú nem determinisztikus VA-t az (a+b)*a(a+b)n-1 nyelvhez! (b)** Mutassuk meg, hogy minden DVA, ami elfogadja ezt a nyelvet legalább 2n állapotú!