Formális nyelvek gyakorlat (4)

2001. március 6., kedd

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

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

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

6. Az $L$ nyelv szavaiban a szavak nem ugyanazzal a betûvel kezdõdnek, mint amivel végzõdnek, így páros számú homogén részsorozat van minden szóban. Párosítva ezeket (az elsõt a másodikkal, a harmadikat a negyedikkel, stb.), minden pár hossza páratlan, tehát a pár egyik tagja páros a másik meg páratlan. Adjunk az $L$ nyelvhez minimálautomatát!

7. Az $L$ nyelv mondatainak hossza osztható hárommal, az üres szó nincs a nyelvben. Ezek szerint a nyelv egy tetszõleges szavának karaktereit hármasával csoportokra oszthatjuk (az elejérõl kezdve). Minden csoportban valamelyik karakter legalább kétszer elõfordul. A nyelvbe azon szavak tartoznak, melyekben ez a többségi karakter a szomszédos csoportokban egymástól különbözik. Szerkesszen minimálautomatát a fenti nyelvre!