Formális nyelvek gyakorlat (6)
2005. október 27., csütörtök
1 . Küszöböljük ki a felesleges szimbólumokat!
,
,
2. Küszöböljük ki a felesleges szimbólumokat!
,
,
,
3. Mi lenne, ha az 1. feladatban előbb csinálnánk a
top-down fésülést?
Tanulság: A sorrend nem mindegy.
4. (Szigorlaton lehet ilyen kérdést kapni)
Miért a gyakorlaton nézett 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?)
5. Jólfésült nyelvtan kell ebből:
,
,
,
6.
(a) Rajzoljuk fel a
szó egy levezetési fáját az
nyelvtanban! Adjuk meg a fához tartozó jobb és ballevezetést!
Egyértelmű-e ez a nyelvtan?
(b) Írjuk át az posztfix alakú kifejezést infix alakba!
(Használjuk a levezetési fát!)
7. Mit generálnak az alábbi nyelvtanok?
Egyértelműek-e a nyelvtanok?
(a)
(b)
(c)
(d)
8. Egészítsük ki az infix aritmetikás egyértelmű nyelvtant a hatványozással
(!
Ennek a precedenciája a legnagyobb és jobbról-balra szabály szerint
értékelődik ki. Adjuk meg a nyelvtant és az
kifejezés levezetési
fáját!
9. Tekintsük a következő nyelvtant:
,
,
,
(a) Egyértelmű-e a által generált nyelv?
(b) Egyértelmű-e a nyelvtan?
10. Adott két nyelv:
,
Készítsen nyelvtant -re!
11. Vegyük a következő nyelvtant, ahol az , és szavak a
nyelvtan terminális szimbólumai:
,
.
(a) Egyértelmű-e a nyelvtan?
(b) Egyértelmű-e a generált nyelv?
12. Az infix alakú aritmetikai kifejezések helyett néha
célszerűbb a prefix vagy posztfix lengyel jelölés használata. Például a csak
összeadást és szorzást használó posztfix lengyel aritmetikai kifejezéseket
az alábbi nyelvtan generálja:
Készíts két egyértelmű nyelvtant, egyet a posztfix egyet meg az infix
alakú Boole-kifejezések generálására, ahol az operátorok a következők:
monadikus, és diadikus operátorok,
ebben a precedencia-sorrendben. A diadikusok balról-jobbra értékelődnek ki.
A precedencia zárójelekkel
felülbírálható, két monadikus operátor nem állhat egymás mellett.