Formális nyelvek gyakorlat (9)

2001. április 10., kedd

1.
(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?
(c) Készíts ballevezetést a $+*aaa$ szóhoz a nyelvtanban és ezt vesd össze a PDA elfogadó működésével!

2.
(a) Adj veremautomatát az $E\ensuremath{\rightarrow}EE+\;\vert\;EE*\;\vert\;a$ nyelvtanhoz az órán tanult második konstrukcióval (ami röntgenszemű PDA-t ad).
(b) Adj egy elfogadó lépéssorozatot az $aa+a*$ szóhoz a PDA-ban! Adj egy nem elfogadót is! Hogy működik a PDA a $+a*$ szón?
(c) Készíts jobblevezetést az $aa+a*$ szóhoz a nyelvtanban és ezt vesd össze a PDA elfogadó működésével!

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

4. Determinisztikus PDA kell a következő nyelvekhez:
$L_1=\{a^mb^nc^n\;\vert\;0\leq m, n\;\}$
$L_2=\{a^mb^mc^n\;\vert\;0\leq m, n\;\}$

5. Igaz-e, hogy minden PDA-hoz lehet vele egyenértékű egyálapotú PDA-t adni?

6. Igaz-e, hogy minden olyan $P$ PDA-ra, melynek vannak elfogadó állapotai az automata által üres veremmel elfogadott nyelv megegyezik az automata által állapottal elfogadott nyelvvel?

7. Egészítsük ki az infix aritmetikás egyértelmű nyelvtant a hatványozással ($\wedge)$!
(A nyelvtan: $E\ensuremath{\rightarrow}E+T\;\vert\;T$, $T\ensuremath{\rightarrow}T*F\;\vert\;F$, $F\ensuremath{\rightarrow}(E)\;\vert\;a$)
Ennek a precedenciája a legnagyobb és jobbról-balra szabály szerint értékelődik ki. Adjuk meg a nyelvtant és az $(a+a)\wedge a*a$ kifejezés levezetési fáját!