Formális nyelvek gyakorlat (3)

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

1. Adjuk meg az alábbi automatához tartozó minimálautomatát!



2. Az alábbi táblázattal adott egy véges automata, melynek 12 állapota van és input ábécéje az $\{a,b\}$ halmaz. Kezdőállapot a $0$, elfogadó állapotok a $0$ és a $8$.
Minimalizáld az automatát!

	0	1	2	3	4	5	6	7	8	9	10	11
a	3	9	11	2	11	6	8	10	1	4	8	4
b	5	4	8	11	4	11	4	4	7	0	4	11

3. Álljon az $L$ nyelv $\{a,b\}^*$ azon szavaiból, melyek ha $a$-ra végződnek, akkor nen tartalmaznak $bb$ részszót, és ha $b$-re végződnek, akkor nem tartalmaznak $aa$ részszót. Készíts minimálautomatát ehhez a nyelvhez!

4. Adjunk minimálautomatát az alábbi nyelvtan által generált nyelvhez

$$\begin{eqnarray*} S &\ensuremath{\rightarrow}& A \mid ab, \\ A &\ensuremath{\ri... ...ghtarrow}& bB \mid C \mid a, \\ C &\ensuremath{\rightarrow}& bb \end{eqnarray*}$$

5. Készítsünk minimálautomatát az alábbi nyelvhez ( $\Sigma=\{a,b\}$):
$L =\{ w : \vert w\vert _a \mbox{ páros}, \vert w\vert _b \mbox{ páros és } \vert w\vert \mbox{ osztható 4-gyel}\}$

6. Legyen $\Sigma=\{a,b\}$ és álljon az $L$ nyelv azokból a legalább 3 hosszúságú szavakból, melyekben minden három hosszú részszó legalább 2 darab $a$ betűt tartalmaz. Készíts minimálautomatát az $L$ nyelvhez! (Ha a szóban kevesebb, mint három betű van, akkor az elfogadandó.)

7. Legyen $\Sigma=\{a,b\}$ és az $L$ nyelvbe tartozzanak azok a szavak, melyekben -ha van egyáltalán- a teljes homogén a-sorozatok hossza páratlan.
Szerkesszen az alábbi nyelvekre minimálautomatát: $L$, $L^2$, $L\cap L^2$, $L^*$.

8. Legyen $L_1$ és $L_2$ az alábbi két nyelv:
$L_1$ azokat a $\Sigma$ feletti szavakat tartalmazza, amelyekben ${\vert w\vert}_a$ és ${\vert w\vert}_b$ is páratlan. Az $L_2$ azon szavakból áll, ahol ${\vert w\vert}_a$ és ${\vert w\vert}_b$ is páros.
(i) Adjon minimálautomatát ${L_1}^2$-re és $L_2$-re!
(ii) Döntse el, hogy ${L_1}^2$ egyenlő-e $L_2$-vel!
(iii) Ha nem azonosak, akkor adjon minimálautomatát a két nyelv szimmetrikus differenciájára!

9. Az $L$ nyelv azon ${\{a,b\}}^*$ feletti szavakból áll, melyekben páratlan sok teljes homogén b-sorozat van.
Készítsen minimálautomatát az $L^2\cap L$ nyelvre!

10. 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^*$!

11. Legyen $L_1$ azon $\{a,b\}$ feletti szavak nyelve, mely szavakban páros sok $a$ van, $L_2$ pedig azon $\{a,b\}$ feletti szavak nyelve, mely szavakban páratlan sok $b$ van.
Adj minimálautomatát az $L_1$, $L_2$, $L_1\cup L_2$, $L_1\cap L_2$, ${L_1}^*$, ${L_2}^*$, $L_1L_2$ és $\overline{L_1}$ nyelvekre!

12. Az $L$ nyelvből képezzük azt a min(L)-lel jelölt nyelvet, ami azon szavakat tartalmazza, melyeknek egyetlen valódi kezdőszelete sincs $L$-ben. Bizonyítsd be, hogy ha $L$ reguláris, akkor min(L) is az.