Sziasztok!

A mai kis zh eredményei.

A mai óra anyaga: CF nyelvtanok jólfésülése. Ez magában foglalja az epszilon-szabályok kiküszöbölését, a láncszabályok kiirtását és végül a felesleges szimbólumok eltüntetését. Ez mind benne van a jegyzetben, amit próbáljatok megszerezni valahonnan.

A feladatok közül az utolsó kettőt nem beszéltük meg, meg egyetlen gyakorlót sem.

Fontos: a héten lesz még feladatmegoldó konzi lesz csütörtök reggel, a szokásos helyen és időben (csütörtök, 8.30, a tanszéken a 134-ben). A következő két héten azonban nem lesz tanítás hétfőnként, azaz a mi óránk is elmarad. Ezek helyett pótóra lesz mindkét héten a konzi helyén/idejében. Nem kötelező jönni, felteszem a web-re, hogy mi hangzik el. Sajnálom, hogy plusz órákat kell berakni, de szerintem még mindig ez a legjobb megoldás. Persze, ha tudtok jobbat, akkor szóljatok bátran.

Formális nyelvek gyakorlat (5)

2000. október 9., hétfő

1. Küszöböljük ki az $\epsilon$-szabályokat!
$S\ensuremath{\rightarrow}SaSb\vert\epsilon$

2. Küszöböljük ki az $\epsilon$-szabályokat!
$S\ensuremath{\rightarrow}ABC$, $A\ensuremath{\rightarrow}BB\vert\epsilon$, $B\ensuremath{\rightarrow}CC\vert a $, $C\ensuremath{\rightarrow}AA\vert b$

3. Küszöböljük ki a láncszabályokat!
$E\ensuremath{\rightarrow}E+T\vert T$, $T\ensuremath{\rightarrow}T*F\vert F$, $F\ensuremath{\rightarrow}(E)\vert a$

4 . Küszöböljük ki a felesleges szimbólumokat!
$S\ensuremath{\rightarrow}a\vert B$, $B\ensuremath{\rightarrow}BC$, $C\ensuremath{\rightarrow}b$

5. Küszöböljük ki a felesleges szimbólumokat!
$S\ensuremath{\rightarrow}A\vert B$, $A\ensuremath{\rightarrow}aB\vert bS\vert b$, $B\ensuremath{\rightarrow}AB\vert Ba$, $C\ensuremath{\rightarrow}AS\vert b$

6. Mi lenne, ha a 4. feladatban előbb csinálnánk a top-down fésülést?
Tanulság: A sorrend nem mindegy.

7. (Szigorlaton lehet ilyen kérdést kapni)
Miért ebben a fenti sorrendben kell elvégezni a jólfésülés három részét? (Azaz ha máshogy csinálnánk, akkor az miért lenne rossz, illetve így miért nem az?)

8. CNF kell.
$S\ensuremath{\rightarrow}aSb\vert ab$

9. Ki kell küszöbölni a közvetlen balrekurziót.
$E\ensuremath{\rightarrow}E+T\vert T$, $T\ensuremath{\rightarrow}T*F\vert F$, $F\ensuremath{\rightarrow}(E)\vert a$

Gyakorló feladatok

10. Küszöböljük ki a láncszabályokat!
$S\ensuremath{\rightarrow}A\vert B$, $A\ensuremath{\rightarrow}B\vert D\vertB\vert 1$, $B\ensuremath{\rightarrow}C$, $C\ensuremath{\rightarrow}B\vert A0$, $D\ensuremath{\rightarrow}C$

11. Jólfésült nyelvtan kell ebből: $S\;\ensuremath{\rightarrow}\; Ba\;\vert\;Cab\;\vert\;A$
$A\;\ensuremath{\rightarrow}\; aB\;\vert\;aC\;\vert\;a$
$B\;\ensuremath{\rightarrow}b\;\vert\;BC$
$C\;\ensuremath{\rightarrow}\;Cb\;\vert\;CA$

12. Chomsky normál alakra kell hozni: $S\;\ensuremath{\rightarrow}\; ABB\;\vert\;a\;\vert\;ba$
$A\;\ensuremath{\rightarrow}\; BaS\;\vert\;aBS$
$B\;\ensuremath{\rightarrow}b\;\vert\;bS$