Formális nyelvek gyakorlat (7) 2001. március 27., kedd 1. Rajzoljuk fel a $aaa*a+a+*$ szó egy levezetési fáját az $E\ensuremath{\rightarrow}EE+\;\vert\;EE*\;\vert\;a$ nyelvtanban! Adjuk meg a fához tartozó jobb és ballevezetést! Egyértelmû-e ez a nyelvtan? 2. Mit generálnak az alábbi nyelvtanok? Egyértelmûek-e a nyelvtanok? (a) $S\ensuremath{\rightarrow}aSb\vert\epsilon$ (b) $S\ensuremath{\rightarrow}SaSb\vert\epsilon$ (c) $S\ensuremath{\rightarrow}SaSbS\vert\epsilon$ 3. Küszöböljük ki az $\epsilon$-szabályokat! $S\ensuremath{\rightarrow}SaSb\vert\epsilon$ 4. 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$ 5. 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$ 6. Mit generálnak az alábbi nyelvtanok? Egyértelmûek-e a nyelvtanok? Egyértelmûek-e a generált nyelvek? (a) $E\ensuremath{\rightarrow}E+E\;\vert\;E*E\;\vert\;(E)\;\vert\;a$ (b) $E\ensuremath{\rightarrow}E+T\;\vert\;T \;\;$, $T\ensuremath{\rightarrow}T*F\;\vert\;F\;\;$, $F\ensuremath{\rightarrow}(E)\;\vert\;a$ 7. Vegyük a következõ nyelvtant, ahol az $if$, $then$ és $else$ szavak a nyelvtan terminális szimbólumai: $S\ensuremath{\rightarrow}if\;\;E\;\;then \;\;S\;\vert\;if \;\;E\;\;then\;\;S\;\;else\;\;S\;\vert\;a$, $E\ensuremath{\rightarrow}b$. (a) Egyértelmû-e a nyelvtan? (b) Egyértelmû-e a generált nyelv? 8. 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$ 9. 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$