Formális nyelvek gyakorlat (2) 2001. február 20., kedd 1. Nézzük a következõ véges automatát, melynek input ábécéje $\{a,b\}$: (a) Mi történik az automatában az $aaa$, $ab$ és $abb$ szavak hatására? (b) Mi az automata által elfogadott nyelv? (c) Alakítsd át az automatát teljesen specifikált automatává (minden állapotban legyen minden karakterre legalább egy kivezetõ nyíl) (d) Alakítsd át úgy az automatát, hogy csak egy végállapota legyen és ebbõl az egy végállapotból ne vezessen nyíl sehova Természetesen a (c) és (d)-beli átalakításkor az elfogadott nyelv nem változhat. 2. Hogyan kell általában úgy átalakítani egy véges automatát, hogy az új automata (a) teljesen specifikált legyen? (b) csak egy végállapotot tartalmazzon és abból ne vezessen sehova se nyíl? 3. Mutasd meg, hogy egy ``elfuserált'' véges automatát, aminek több kezdõállapota van, mindig át lehet alakítani egy olyanná, aminek csak egy van és abba se vezet be nyíl. 3. Adjunk (lehetõleg 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$\}$. 4. Adjunk (lehetõleg determinisztikus) véges automatát ahhoz az $\{a,b\}$ feletti nyelvhez, melybe azon szavak tartoznak, amelyekben minden teljes homogén $a$-sorozat hossza osztható 3-mal és minden teljes homogén b-sorozat hossza osztható 2-vel. 5. Adjunk véges automatát (a) az üres nyelvre, azaz $L=\emptyset$, (b) a csak az $\epsilon$-t tartalmazó nyelvre, azaz $L=\{\epsilon\}$. 6. Legyen $\Sigma=\{a,b,c\}$. A nyelv szavaira a következõ két dolog igaz: $(i)$ összesen páratlan sok karakter van bennük $(ii)$ $a$ után közvetlenül nem jöhet $c$, $b$ után $a$, $c$ után $b$. Véges (lehetõleg determinisztikus) automata kell erre a nyelvre. 7. 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.