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$