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