Gyakorló feladatok formális nyelvekbõl 1. gyakorlat 1. Mely szavakból áll az a nyelv, amelyet az alábbi reguláris kifejezés ír le: (a+b)*[aa(a+b)*bb+bb(a+b)*aa](a+b)* ? Adjunk meg ehhez a nyelvhez egy véges automatát! 2. Igaz-e, hogy (a*+b*)(b*+a*)=(a+b)* ? 3. Adjunk reguláris nyelvtant az (a+b)*(aa+bb)(a+b)* nyelvhez! 4. Keressünk CF nyelvtant a palindrómák nyelvére $\{a,b\}$ felett (azaz $\{w \mid w = w^{-1}\}$)! 5. Adjunk meg egy CF nyelvtant, amely a helyes zárójelezéseket generálja! (Tehát most $\Sigma = \{\,(\, , \,)\,\}$, és azokat a zárójelekbõl álló sorozatokat kell elõállítani, melyekben a nyitó és csukó zárójelek száma azonos, továbbá semelyik kezdõszelet sem tartalmazhat több csukó zárójelet, mint ahány nyitó van benne.) 6. Nyelvtan kell az $\{a^{2^n}\;\vert\;n\geq 0\}$ nyelvre. 7. Mi a generált nyelv? $S\ensuremath{\rightarrow} AB \vert CD$, $A\ensuremath{\rightarrow} aAb \vert aEb$, $B\ensuremath{\rightarrow} Bc \vert c$, $C\ensuremath{\rightarrow} Ca \vert a$, $D\ensuremath{\rightarrow} bDc \vert bFc$, $E\ensuremath{\rightarrow} Eb \vert b$, $F\ensuremath{\rightarrow} FC \vert c$ 8. Adott az alábbi nyelvtan: $$\begin{eqnarray*}S& \ensuremath{\rightarrow} & ABBSccc\;\vert\;ABBccc\\ Bc&\ens... ...uremath{\rightarrow} &AB \\ Ab & \ensuremath{\rightarrow} & ab \end{eqnarray*}$$ Adja meg a generált nyelvet! 9. Hogyan megy a nyelvbe tartozást eldöntõ algoritmus az anbncn nyelv és az a2b3c3 szó esetén? 10. Lássuk be, hogy a CS nyelvtanokra adott két definíció ekvivalens, azaz ha adott egy nyelvtan, ami nem-csökkentõ szabályokból áll, (plusz esetleg az $S\ensuremath{\rightarrow}\epsilon$, de akkor az S nem áll szabály jobb-oldalán) akkor van egy ugyanezt a nyelvet generáló olyan nyelvtan, ami csupa ${\gamma}_1A{\gamma}_2\ensuremath{\rightarrow} {\gamma}_1z{\gamma}_2$ alakú szabályból áll, ahol $z\not=\epsilon$ (plusz esetleg az $S\ensuremath{\rightarrow}\epsilon$, de akkor az S nem áll szabály jobb-oldalán) és megfordítva.