Általános és regulárisos feladatok 1. (i) Adjunk 0-s nyelvtant az alábbi nyelvhez: $\{x\in {\{a,b\}}^*\;\vert\;x$ nem $ww$ alakú $\}$ ** (ii) Adjunk CF nyelvtant is hozzá. * 2. Mutassuk meg, hogy minden DVA, ami elfogadja a ${(a+b)}^*a{(a+b)}^{n-1}$ nyelvet legalább $2^n$ állapotú, noha nemdeterminisztikus véges automata már van $n+1$ állapottal is! * 3. Nyelvtan kell az $\{a^{F(n)}\;\vert\;n\geq 1, F(n)$ az $n$-edik Fibonacci szám $\}$ nyelvre. (Nem baj, ha 0-s lesz a nyelvtan) ** 4. Nyelvtan kell az $\{a^{p}\;\vert\;p$ prím szám $\}$ nyelvre. (Itt se baj, ha 0-s lesz a nyelvtan, sõt mar az is jó, ha nagyjából el tudod mesélni, hogy hogyan mûködjön a nyelvtan, nem kell rögtön szabályokra lebontva leírni.) *** 5. Regulárisak-e az alábbi nyelvek? $L_1 = \{xx^Rw\;\vert\; x\in {\{0,1\}}^+, w\in {\{0,1\}}^*\}$ $L_2 = \{xwx^R\;\vert\; x\in {\{0,1\}}^+, w\in {\{0,1\}}^*\}$ Az egyik nem is csillagos, a másik meg **. 6. Regulárisak-e a következõ nyelvek? $\{0^i1^j \;\vert\; lnko(i,j)\not = 1\}$ ** $\{0^{F(n)}\;\vert\; F(n)$ az $n$-edik Fibonacci-szám$\}$ * 7. Vigyázat, ez nem igaz!!! Valamit elrontottam, nem ezt a példát akartam kitûzni. Így két feladat van: (a) Miért nem igaz? (b) Milyen plusz feltételekkel lehet igaz ez? A feladat eredeti formájában: Tegyük fel, hogy az $L_1$ nyelv reguláris, az $L_2$ nyelv pedig nem reguláris. Igazoljuk, hogy ekkor $L_1L_2$ sem reguláris! ** 8. Legyen $L$ egy reguláris nyelv a $\Sigma$ ábécé felett. $0.5 \;L=\{x\in {\Sigma}^*\;\vert\;\exists y \in {\Sigma}^*, \vert y\vert=\vert x\vert, \;xy\in L\}$. Azaz $0.5 \;L$-ben az $L$-beli szavak elsõ felei vannak. Reguláris-e az $0.5 \;L$ nyelv? ** és fél * 9. Bizonyítsd be, hogy ha $L\subseteq 0^*$ és $L$ CF nyelv, akkor $L$ reguláris is! Most éppen én se tudom, hogyan megy, valószínûleg igen nehéz = ****