Sziasztok! Az alábbi feladatokon kívül az óra anyaga volt még az, hogy megszámlálhatóan végtelen sok generatív nyelv van egy adott véges ábécé felett . A feladatokból voltak az 1., 2., 4a, 5., 6., 7. Házi feladat a 4c, ezt mindenképpen megbeszéljük, a többi kimaradt példa meg gyakorlásnak van. Formális nyelvek gyakorlat 2000. szeptember 11. 1. Milyen nyelvet ír le az alábbi kifejezés? (a+b)*(aa+bb)(a+b)*= 2. (i) Adjunk generatív nyelvtant, amely a $\{w_1,\ldots,w_n\}$ véges nyelvet generálja! (ii) A fenti nyelvhez adjunk reguláris nyelvtant. 3. Adjunk minél egyszerûbb (alacsonyabb osztályú) nyelvtant ahhoz a nyelvhez, ami azon szavakat tartalmazza, melyek tartalmazzák a baba részszót! 4. Adjuk meg CF nyelvtannal az alábbi nyelveket! (a) $\{{a^nb^n}\;\vert\;n\geq 0\;\}$ (b) $\{a^ib^ic^j, a^{i}b^jc^j\;\vert\;i,j\geq 1\;\}$ (c) $\{a^mb^n\;\vert\;m\leq n\leq 3m\;\}$ 5. Mit generál az alábbi nyelvtan? $S\;\ensuremath{\rightarrow}\; aS\;\vert\;bS\;\vert\;cS\;\vert\;cA$, $A\;\ensuremath{\rightarrow}\; cB$, $B\;\ensuremath{\rightarrow}\; aB\;\vert\; bB\;\vert\;cB \vert\; \epsilon$ 6. Mi a generált nyelv? $S\ensuremath{\rightarrow} AB \vert \epsilon$, $A\ensuremath{\rightarrow} aAb \vert \epsilon$, $B\ensuremath{\rightarrow} bBc \vert \epsilon$ 7. Adott az alábbi nyelvtan: $$\begin{eqnarray*}S& \ensuremath{\rightarrow} & BXB\\ X&\ensuremath{\rightarrow}... ...ensuremath{\rightarrow} &aB\\ BB & \ensuremath{\rightarrow} &a \end{eqnarray*}$$ Adja meg a generált nyelvet és ismertesse a nyelvtan gondolatmenetét! 8. Kérdések: (a) Hány generatív grammatika van? (b) Hány generatív nyelv van? (c) Hány reguláris nyelv van? Nehezebb, de érdekes feladat 9. Keressünk CF nyelvtant az alábbi nyelvhez: $\{x\in {\{a,b\}}^*\;\vert\;x$ nem ww alakú $\}$ (Ha CS-t sikerül adni, az se rossz.)