Formális nyelvek gyakorlat

2005. szeptember 15., csütörtök

1. Milyen nyelvet ír le az alábbi kifejezés?
(a) ${(a+b)}^*(aa+bb){(a+b)}^*=$
(b) ${(ab)}^+=$

2. 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$

3. Na és ez?
$S\ensuremath{\rightarrow}aSBC\;\vert\;abC, CB\ensuremath{\rightarrow}BC, bB\ensuremath{\rightarrow}bb, bC\ensuremath{\rightarrow}bc, cC\ensuremath{\rightarrow}cc$

4. (i) Adjunk generatív nyelvtant, amely a $\{a,ab,bbb,ba\}$ véges nyelvet generálja!
(ii) A fenti nyelvhez adjunk reguláris nyelvtant.
(iii) Igaz-e, hogy minden véges nyelv reguláris?

5. Adjunk minél egyszerűbb (alacsonyabb osztályú) nyelvtant ahhoz a nyelvhez, ami azon szavakat tartalmazza, melyek a $\Sigma=\{a,b\}$ ábécé felett vannak és
(a) tartalmazzák a $baba$ részszót!
(b) páros hosszúak!

6. 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\;0\leq m\leq n\leq 3m\;\}$

7. Mi a generált nyelv?
$S\ensuremath{\rightarrow}AB \vert \epsilon $, $A\ensuremath{\rightarrow}aAb \vert \epsilon$, $B\ensuremath{\rightarrow}bBc \vert \epsilon$

8. Adott az alábbi nyelvtan:

\begin{eqnarray*} S& \ensuremath{\rightarrow}& BXB\\ X&\ensuremath{\rightarrow}... ... \ensuremath{\rightarrow}&aB\\ BB & \ensuremath{\rightarrow}&a \end{eqnarray*}



Add meg a generált nyelvet és ismertesd a nyelvtan gondolatmenetét!

9. Adott véges ábécé felett
(a) hány generatív grammatika van?
(b) hány generatív nyelv van?
(c) hány reguláris nyelv van?

Nehezebb, de érdekes feladatok

10. 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.)

11. Nemcsökkentőnek nevezünk egy nyelvtant, ha benne minden szabály baloldala legfeljebb olyan hosszú mint a jobboldala (kivéve esetleg az $S\ensuremath{\rightarrow}\epsilon$ szabályt, de ha ilyen van a nyelvtanban, akkor az $S$ nem szerepelhet szabály jobboldalán). Bizonyítsd be, hogy a nemcsökkentő nyelvtanok éppen a környezetfüggő nyelveket generálják.