6. gyakorlat

1. feladat Alakítsuk Greibach normál alakra a következõ nyelvtant! S -> AS | b A -> SA | aa 2. feladat Rajzoljuk fel az aaa*a+a+* szó egy levezetési fáját az E -> EE+ | EE* | a nyelvtanban! Egyértelmû-e ez a nyelvtan? Írjuk át az aaa*a+a+* posztfix alakú kifejezést infix alakba! 3. feladat Adjunk CF nyelvtant az alábbi nyelvekhez: {aibjck | i+k=j, i,j,k >= 0} {aibj | 0 <= i <= j <= 3i} 4. feladat Milyen nyelvet generál az alábbi nyelvtan? S -> AB | CD A -> aAb | aEb B -> Bc | c C -> Ca | a D -> bDc | bFc E -> Eb | b F -> Fc | c 5. feladat Az infix aritmetika elõadáson tanult nyelvtanát egészítsd ki a következõ mûvelettel: Hatványozás, melynek precedenciája nagyobb a szorzásénál és jobbról balra szabály szerint értékelõdik ki. Miután megszerkesztetted az új nyelvtant, szerkeszd meg az (a+a)^a*a kifejezés levezetési fáját is. 6. feladat Vegyük a következõ nyelvtant: S -> if E then S | if E then S else S | a E -> b Egyértelmû a nyelvtan? Egyértelmû a nyelvtan által generált nyelv? 7. feladat Adjunk automatát arra a nyelvre, melyben az a-k száma megegyezik a b-k számával az a-k és a b-k száma legfeljebb eggyel térhet el egymástól az a-k és a b-k száma legfeljebb k-val térhet el egymástól minden prefixben 8. feladat Tekintsük az infix aritmetika ismert nyelvtanát! Szerkesszünk hozzá veremautomatát, amely a baloldali a jobboldali levezetést valósítja meg. Elemezzük mindkét veremautomatával az (a+a)*a mondatot! 9. feladat Adottak az alábbi nyelvek (i,j >= 0): ai+jbi cj aibi+j cj aibj ci+j Készíts rájuk CF nyelvtant!

Varró Gergely gervarro@cs.bme.hu

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