5. gyakorlat

1. feladat Küszöböljük ki az epszilon-szabályokat! S -> SaSb | epszilon 2. feladat Küszöböljük ki az epszilon-szabályokat! S -> ABC A -> BB | epszilon B -> CC | a C -> AA | b 3. feladat Küszöböljük ki a láncszabályokat! E -> E+T | T T -> T*F | F F -> (E) | a 4. feladat Küszöböljük ki a felesleges szimbólumokat! S -> a | B B -> BC C -> b 5. feladat Küszöböljük ki a felesleges szimbólumokat! S -> A | B A -> aB | bS | b B -> AB | Ba C -> AS | b 6. feladat Fésüljük meg az alábbi nyelvtant! S -> Ba | Cab | A A -> aB | aC | a B -> b | BC C -> Cb | CA 7. feladat Fésüljük meg az alábbi nyelvtant! S -> aS | aA A -> BC B -> epszilon C -> AB | bD | b D -> DE E -> b Mi történne, ha az eljárásunk során két lépés sorrendjét felcserélnénk? 8. feladat Alakítsd Chomsky normál alakra a következõ nyelvtant: S -> ABB | a | ba A -> BaS | aBS B -> b | bS 9. feladat Alakítsd Chomsky normál alakra! S -> aSb | ab 10. feladat Alakítsd Chomsky normál alakra! S -> aSa | bSa | epszilon 11. feladat Hozd Greibach normál alakra a következõ nyelvtant! S -> AB | B A -> AS | a B -> SB | b 12. feladat Adott a következõ környezetfüggetlen nyelvtan: S -> SaSaSb | epszilon Írd le verbálisan, hogy milyen nyelvet generál a fenti nyelvtan, és állapítsd meg, hogy egyértelmû-e. 13. feladat Adott a következõ nyelvtan: S -> aaSSS | abS | b Írd le verbálisan, hogy milyen nyelvet generál ez a nyelvtan, és állapítsd meg, hogy egyértelmû-e!

Varró Gergely gervarro@cs.bme.hu

Utolsó módosítás dátuma: 2004. március 8.