Formális nyelvek gyakorlat 2001. február 13., kedd 1. Adjunk olyan nyelvtant, amely azon $\{a,b\}$ feletti szavakat generálja, melyek (a) $a$-val kezdõdnek (b) $a$-val kezdõdnek és $b$-vel végzõdnek (c) nem ugyanazzal a betûvel kezdõdnek, amivel végzõdnek 2. (a) Adjunk generatív nyelvtant, amely a $\{w_1,\ldots,w_n\}$ véges nyelvet generálja! (b) 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! Nehezebb, de érdekes feladat 8. 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.)