Formális nyelvek gyakorlat (7)

2005. november 3., csütörtök

1. PDA kell ahhoz a nyelvhez, melynek ábécéje az $\{a,b\}$ és szavaiban az $a$ és a $b$ karakterek száma megegyezik.

2. Automata kell (első kérdés, hogy milyen?):
$\{a^ib^jc^k\;\vert\;i+k=j\geq 0\;\}$

3. Determinisztikus PDA kell a következő nyelvhez:
$L_1=\{a^mb^nc^n\;\vert\;1\leq m, n\;\}$

4. Az $L_1$ és az $L_2$ nyelveket is az definiálja, hogy bennük az $ab$ és a $ba$ minirészsorozatok száma azonos. Viszont $L_1$ ábécéje az $\{a,b\}$, $L_2$-é pedig az $\{a,b,c\}$. Mindkét nyelvre kell automata vagy nyelvtan.

5. PDA kell a következő nyelvhez:
$\{a^mb^n\;\vert\;1\leq m\leq n\leq 2m\;\}$

6. Tervezzen automatát azon $\Sigma=\{a,b\}$ feletti nyelvhez, melynek szavaiban a magányos b-k száma meghaladja az egynél hosszabb homogén a sorozatok számát.

7. A kétirányú PDA, olyan mint a sima PDA, csak bír visszafele is menni. (Ahogy a 2VA-nál volt.) Akkor fogad el, ha végigolvassa a szót és elfogadó állapotba kerül. Kérdés: erősebb-e ez, mint a sima PDA?
(Segítség: az $a^nb^nc^n$ nyelv nem CF nyelv.)

8. (a) Adj veremautomatát az $E\ensuremath{\rightarrow}+EE\;\vert\;*EE\;\vert\;a$ nyelvtanhoz az órán tanult első konstrukcióval (ami nem röntgenszemű PDA-t ad).
(b) Adj egy elfogadó lépéssorozatot a $+*aaa$ szóhoz a PDA-ban! Adj egy nem elfogadót is! Hogy működik a PDA a $+*a$ szón?

9. Környezetfüggetlen-e az alábbi nyelv? (Ha igen, akkor adj PDA-t hozzá, ha nem, akkor bizonyítsd be ezt!)
$L=\{a^ib^jc^k\;\vert\;0\leq i\leq j\leq k\}$

10. Igazak-e az alábbi állítások? Az indoklás nem elhanyagolható része a válasznak.

1. Minden többállapotú PDA-hoz létezik vele egyenértékű egyállapotú PDA.
2. Egy reguláris nyelv minden részhalmaza reguláris.
3. Ha az $L_1, \ldots ,L_n$ nyelvek ($n\geq 1$) regulárisak, akkor az ${\cup}_{i=1}^nL_i$ nyelv is reguláris.
4. Megszámlálhatóan végtelen sok reguláris nyelv uniója nem feltétlenül reguláris
5. Megszámlálhatóan végtelen sok reguláris nyelv uniója lehet reguláris
6. Attól. hogy $L_1$ és $L_2$ nem reguláris, $L_1\cup L_2$ még lehet reguláris
7. $(r^*+s^*)(s^*+r^*)={(r+s)}^*$