Nehezebb/érdekesebb feladatok CF-es feladatok 1. Mutasd meg, hogy egy $L$ nyelv elfogadható üres veremmmel elfogadó determinisztikus PDA-val pontosan akkor, ha elfogadható állapottal elfogadó determinisztikus PDA-val és a nyelv prefix tulajdonságú! ** 2. Veszítenének-e a PDA-k az erejükbõl, ha megtiltanánk az $\epsilon$- mozgásokat? Ez két kérdés: mi van az állapottal elfogadás és mi van az üres veremmel elfogadás esetén? *** 3. Az $\{x\in {\{a,b,c\}}^*\;\vert\; {\vert x\vert}_a={\vert x\vert}_b={\vert x\vert}_c\}$ nyelv nem CF nyelv. (A pumpálási lemmát kell élesíteni) ** 4. Az $L=\{a^ib^ic^j\;\vert\;i,j\geq 1, i\not= j\}$ nyelv nem CF nyelv. (Itt is célhoz vezet a lemma élesítése) ** 5.(a) Az $\{a^nb^n\;\vert\;n\geq 1\}\cup\{a^nb^{2n}\;\vert\;n\geq 1\}$ nyelv CF. Lásd be ezt! (b) Bizonyítsd be, hogy nem lehet determinisztikus PDA-val elfogadni! Sok csillag = nem tudom a megoldását 6. Mutasd meg, hogy az $\{0^n1^m2^n\;\vert\;n,m\geq 1\}\cup\{0^n1^{m}2^m\;\vert\;n,m\geq 1\}$ nyelvet nem lehet determinisztikus PDA-val elfogadni! (Valószínûleg hasonlóan megy, mint az elõzõ) Sok csillag = nem tudom a megoldását 7. CF nyelvek-e az alábbiak? (a) $\{a^nb^m\;\vert\;n\not =m$ és $n\not =2m\}$ (b) ${(a+b)}^*\setminus \{{(a^nb^n)}^n\;\vert\;n\geq 1\}$, (c) $\{ww^{-1}w\;\vert\;w\in {(a+b)}^*\}$ *