Sziasztok!

A mai óra anyaga: (a módszerek pontosan le vannak írva a jegyzetben)

1. Chomsky normál formára hozás: ez azt jelenti, hogy elérjük, hogy a CF (környezetfüggetlen) nyelvtan minden szabálya $A\ensuremath{\rightarrow}a$ vagy $A\ensuremath{\rightarrow}BC$ alakú legyen, ahol $A,B,C\in N$ és $a\in \Sigma$. (Meg esetleg lehet még $S\ensuremath{\rightarrow}\epsilon$ szabály is, de ekkor $S$ nem szerepelhet szabály jobboldalán) (Persze mindezt úgy, hogy a generált nyelv ne változzon.)
Ehhez gyakorló példa a múltkori feladatsor 8. feladata.

2. A közvetlen balrekurzió kiküszöbölése: Egy nyelvtan rekurzív, ha van olyan $A\in N$ nemterminális, hogy $A{\ensuremath{\rightarrow}}^+\ldots A\ldots$, azaz, ha $A$-ból le lehet vezetni olyan szót, amiben $A$ szerepel. Ezt nem lehet megszüntetni úgy, hogy alakítgatjuk a nyelvtant, mert a nyelvtan rekurzív volta azzal ekvivalens, hogy a generált nyelv végtelen. (Meggondolni esetleg!!)
Meg lehet viszont szüntetni egy nyelvtan balrekurzivítását, azaz azt, hogy legyen olyan $A\in N$ nemterminális, hogy $A{\ensuremath{\rightarrow}}^+A\ldots$, azaz, hogy $A$-ból le lehessen vezetni olyan szót, ami $A$-val kezdődik. (Ezt azért fontos megszüntetni, mert az elemzők nagy része, amiket használunk, nem megy, ha a nyelvtan balrekurzív.)
Először az úgynevezett közvetelen balrekurziót küszöböljük ki: ez az, hogy van a nyelvtanban $A\ensuremath{\rightarrow}A\alpha$ szabály, azaz olyan szabály, ahol a jobboldal ugyanavval a nemterminálissal kezdődik, ami a baloldalon áll.
Ehhez gyakorló példa a múltkori sor 9. feladata.

3. Greibach normál formára hozás: ez azt jelenti, hogy csak $A\ensuremath{\rightarrow}aW$ alakú szabályokat akarunk (meg persze esteleg $S\ensuremath{\rightarrow}\epsilon$, de akkor...), ahol $A\in N, a\in \Sigma, W\in N^*$. Azaz azt akarjuk, hogy minden szabály jobboldala terminálissal kezdődjön. (Ez megoldja a balrekurzió problémáját is, látjátok, ugye?)
Ehhez feladatok a mostani 1. és a gyakorlós 5. feladat.

4. Felelevenítettük az előadásról a levezetési fa, jobb és ballevezetés, egyértelmű, nem egyértelmű CF nyelvtan /CF nyelv fogalmakat. Ezekhez van a többi példa. Órán volt a 2. és a 3b nagyjából. A 3d-t megbeszéljük, a többit majd, ha kéritek.

Formális nyelvek gyakorlat (6)

2000. október 18., szerda

1. GNF kell: $S\ensuremath{\rightarrow}AS\;\vert\; b$, $A\ensuremath{\rightarrow}SA\;\vert\;aa$

2. (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!)

3. 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$ megoldás html-bn és ps-ben
(c) $S\ensuremath{\rightarrow}SaSbS\vert\epsilon$
(d) $S\ensuremath{\rightarrow}SaSbSa\vert\epsilon$

4. 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!

Gyakorlásnak...


5. GNF kell: $A\ensuremath{\rightarrow}BC$, $B\ensuremath{\rightarrow}CA\vert b$, $C\ensuremath{\rightarrow}AB\vert a$

6. 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!

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

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

9. 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.
A posztfix nyelvtant add meg GNF-ban is!