Á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?
  1. $L_1 = \{xx^Rw\;\vert\; x\in {\{0,1\}}^+, w\in {\{0,1\}}^*\}$
  2. $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?
  1. $\{0^i1^j \;\vert\; lnko(i,j)\not = 1\}$ **
  2. $\{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 = ****