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. és a 6., ezek valamelyike házi. A 10. feladatot lapon lehet beadni.

Formális nyelvek gyakorlat (2)

2000. szeptember 20., szerda

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!!
\includegraphics{r4.eps}

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:

\includegraphics{r3uj.eps}
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ú!