Formális nyelvek gyakorlat (2)

2005. szeptember 22., csütörtök

1. Adjunk determinisztikus véges automatát az alábbi nyelvhez:
$L=\{w\in {\{a,b\}}^*\;\vert\;{\vert w\vert}_a$ osztható hárommal, ${\vert w\vert}_b$ osztható kettővel$\}$.

2. Legyen $\Sigma=\{a,b,c\}$. A nyelv szavaira a következő két dolog igaz:
$\bullet$ összesen páratlan sok karakter van bennük
$\bullet$ $a$ után közvetlenül nem jöhet $c$, $b$ után $a$, $c$ után $b$.
Determinisztikus véges automata kell erre a nyelvre.

3. Tegyük determinisztikussá az alábbi automatát!!



4. Adjunk (jobb- és bal-)reguláris nyelvtant a 3. feladat automatájához!

5. Legyen $\Sigma=\{0,1\}$. A jelsorozatokat tekintsük mint bináris számokat. Adjunk automatát, amely pont a hárommal osztható számokat fogadja el! Vegyük figyelembe, hogy szám 0-val nem kezdődik, kivéve ha az maga a 0.

6. Determinizálni kell ezt:



7. 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).

8. Adjunk véges automatát
(a) az üres nyelvre, azaz $L=\emptyset$,
(b) a csak az $\epsilon$-t tartalmazó nyelvre, azaz $L=\{\epsilon\}$.

9. 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$\}$.

10. Determinisztikus véges automata kéretik:
$L=\{w\in {\{a,b\}}^*\;\vert\;$ $w$-ben jobbról a 3. betű b$\}$

11. Készítsünk véges automatát, ami ugyanazt a nyelvet fogadja el, mint amit az alábbi jobbreguláris nyelvtan generál:
$S\ensuremath{\rightarrow}aS\;\vert\;bB\;\vert\;b$
$A \ensuremath{\rightarrow}aA\;\vert\;a\;\vert\;bC$
$B \ensuremath{\rightarrow}bB\; \vert\; b\; \vert\; aA\; \vert\; a$
$C \ensuremath{\rightarrow}bC\; \vert\; aS$

12. Készítsünk véges automatát, ami ugyanazt a nyelvet fogadja el, mint amit az alábbi balreguláris nyelvtan generál:
$S \ensuremath{\rightarrow}Sb\; \vert\; Aa\; \vert\; a$
$A \ensuremath{\rightarrow}Sa \;\vert \;Bb$
$B \ensuremath{\rightarrow}Ba \;\vert\; Bb \;\vert \;\epsilon$

13. 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 $2^n$ állapotú!