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 19., csütörtök 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-ben é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!