Formális nyelvek gyakorlat (6)

2005. október 27., csütörtök

1 . Küszöböljük ki a felesleges szimbólumokat!
$S\ensuremath{\rightarrow}a\vert B$, $B\ensuremath{\rightarrow}BC$, $C\ensuremath{\rightarrow}b$

2. 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$

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: $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$

6. (a) 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?
(b) Írjuk át az $aaa*a+a+*$ 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) $S\ensuremath{\rightarrow}aSb\vert\epsilon$
(b) $S\ensuremath{\rightarrow}SaSb\vert\epsilon$
(c) $S\ensuremath{\rightarrow}SaSbS\vert\epsilon$
(d) $S\ensuremath{\rightarrow}SaSbSa\vert\epsilon$

8. Egészítsük ki az infix aritmetikás egyértelmű nyelvtant a hatványozással ($\wedge)$! Ennek a precedenciája a legnagyobb és jobbról-balra szabály szerint értékelődik ki. Adjuk meg a nyelvtant és az $(a+a)\wedge a*a$ kifejezés levezetési fáját!

9. Tekintsük a következő $G$ nyelvtant:
$S \ensuremath{\rightarrow}A \mid B \mid bbS$, $A \ensuremath{\rightarrow}aB \mid bSA \mid b$, $B \ensuremath{\rightarrow}AB \mid BC$, $C \ensuremath{\rightarrow}AS \mid bB \mid a$
(a) Egyértelmű-e a $G$ által generált nyelv?
(b) Egyértelmű-e a $G$ nyelvtan?

10. Adott két nyelv:
$L_1=\{\;w\in {\{a,b\}}^*\;\vert\; 3\;\vert\;{\vert w\vert}_a, 4\;\vert\;{\vert w\vert}_b\;\}$, $L_2= \{\;w\in {\{a,b\}}^*\;\vert\; w=w^R\;\}$
Készítsen nyelvtant $L_1\cap L_2$-re!

11. 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?

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:
$E\ensuremath{\rightarrow}EE+\vert EE*\vert a$
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: $\neg$ monadikus, $\cup$ és $\cap$ 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.