Gyakorló feladatok... Kezdőknek 1. (a) Írjuk át az aaa*a+a+* posztfix alakú kifejezést infix alakba! (b) Rajzoljuk fel a fenti szó egy levezetési fáját az $E\ensuremath{\rightarrow} EE+\;\vert\;EE*\;\vert\;a$ nyelvtanban! Egyértelmů-e ez a nyelvtan? 2. Legyen a nyelvtanunk a következő: $S\ensuremath{\rightarrow} aB\;\vert\;bA$, $A\ensuremath{\rightarrow} a\;\vert\;aS\;\vert\;bAA$, $B\ensuremath{\rightarrow} b\;\vert\;bS\;\vert\;aBB$. (a) Adjuk meg az aaabbabbba szó egy ballevezetését, egy jobblevezetését és egy levezetési fáját! (b) Egyértelmű-e a nyelvtan? Középhaladóknak 3. Az $S\ensuremath{\rightarrow} XY$, $X\ensuremath{\rightarrow} aXb\;\vert\;ab$, $Y\ensuremath{\rightarrow} bYc\;\vert\;bc$ nyelvtanhoz készítsünk PDA-t, mindkét konstrukcióval, amit tanultunk! 4. Mi lenne, ha két vermet engednénk meg? Azaz, ha a veremautomata szabályai $Q\times(\epsilon\cup \Sigma)\times {\Gamma}_1\times {\Gamma}_2\ensuremath{\rightarrow} Q\times {{\Gamma}_1}^*\times {{\Gamma}_2}^*$ alakúak volnának? Növekedne-e az automata ereje? (Hint: Az anbncn nyelv nem CF.) 5. Az ismert $E\ensuremath{\rightarrow} E+T\;\vert\;T$, $T\ensuremath{\rightarrow} T*F\;\vert\;F$, $F\ensuremath{\rightarrow} (E)\;\vert\;a$ nyelvtan generál felesleges zárójeleket. Például az (a*a)+a generálásakor. Alakítsuk át úgy a nyelvtant, hogy ne tegye ezt! Haladóknak 6. Ha L CF nyelv, akkor van olyan állapottal elfogadó PDA, ami ezt a nyelvet fogadja el, csak két állapota van és nincsenek benne $\epsilon$-szabályok. Ezt kell belátni. Igaz-e ez üres veremmel elfogadó PDA-ra is? 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? (Hint: az anbncn nyelv még mindig nem CF nyelv.) 8. (a) Az $\{a^nb^n\;\vert\;n\geq 1\}\cup\{a^nb^{2n}\;\vert\;n\geq 1\}$ nyelv CF. Lásd be ezt! (b) Nagyon haladóknak Bizonyítsd be, hogy nem lehet determinisztikus PDA-val elfogadni! Cseles kérdések: Igazak-e az alábbi állítások? Az indoklás nem elhanyagolható része a válasznak. 1. Egy reguláris nyelv minden részhalmaza reguláris. 2. Ha az $L_1, \ldots ,L_n$ nyelvek ($n\geq 1$) regulárisak, akkor az ${\cup}_{i=1}^nL_i$ nyelv is reguláris. 3. Megszámlálhatóan végtelen sok reguláris nyelv uniója nem feltétlenül reguláris 4. Megszámlálhatóan végtelen sok reguláris nyelv uniója lehet reguláris 5. Megszámlálhatóan végtelen sok reguláris nyelv van 6. Attól. hogy L1 és L2 nem reguláris, $L_1\cup L_2$ még lehet reguláris 7. (r*+s*) (s*+r*)=(r+s)* 8. Ha L reguláris, akkor az $L'=\{ww\;\vert\;w\in L\}$ nyelv is reguláris, hiszen L'=L2 9. Ha L reguláris, akkor L-1 is reguláris 10. Ha L egy reguláris nyelv a $\Sigma$ ábécé felett, akkor az $L'=\{w\in{\Sigma}^*\;\vert\;\exists x\in L:\vert x\vert=\vert w\vert\}$ nyelv is reguláris. 11. Ha M egy PDA, akkor Lu=La, ahol Lu azon nyelv, amit az automata üres veremmel elfogad, míg La az a nyelv, amit végállapottal elfogad. 12. Ha L egy CF nyelv és $\epsilon\in L$, akkor van olyan L-t generáló nyelvtan, ami pontosan egy $\epsilon$-szabályt tartalmaz. A megoldás: N, I, I, I, I, I, N, N, I, I, N, I