Határidő: 2022-03-15 24:00

• A szélességi keresés arra is alkalmas, hogy egy környezetfüggetlen nyelvtanban levezetést adjuk egy szóhoz.
  1. Tekintsük a \(G = (V, \Sigma, R, S)\) CF nyelvtant, és képezzük a \(\vec{G} = ((V \cup \Sigma)^*, \vec{E})\) irányított gráfot, melynek csúcsai a terminális és nemterminális szimbólumokból képzett sztringek. Ennek a gráfnak megszámlálhatóan végtelen csúcsa van, de ezek közül elég lesz véges sokat bejárni, hogy egy levezetést találjunk.
  2. A \(\vec{G}\) gráf akkor és csakis akkor tartalmazza az \((\alpha, \beta)\) élt, ha az \(\alpha \in (V \cup \Sigma)^*\) sztringből egy bal-levezetési lépéssel (az \(\alpha\) sztringben legelőször előforduló nemterminális szimbólumra egy levezetési lépés alkalmazásával) elérhető a \(\beta \in (V \cup \Sigma)^*\) sztring. Formálisan, \begin{equation*} (\alpha, \beta) \in \vec{E} \Longleftrightarrow \exists w \in \Sigma^* \; \exists \gamma, \delta \in (V \cup \Sigma)^* \; \exists A \in V \colon (A \rightarrow \delta) \in R, \alpha = wA\gamma \textrm{ és } \beta = w\delta\gamma. \end{equation*}
  3. Ebben a gráfban a \(w \in L(G)\) szó bal-levezetései épp az \(S \leadsto w\) utak, ahol \(S \in V\) a kezdő változó. Az út minden éle megfelel valamelyik \(R\)-beli szabály alkalmazásának a legbaloldalibb nemterminális szimbólumra. A feladatban egy ilyen utat szeretnénk megkeresni.
• A cf_hu.py fájlban megadtuk a levezetést kereső program vázát. A program egyetlen parancssori argumentumot vár, a levezetendő szót. A megtalált levezetést a standard kimenetre írja.

  A programban egy egyszerű módszerrel oldottuk meg a terminális és nemterminális szimbólumok különválasztását: az angol ábécé minden A–Z nagybetűjét lehetséges nemterminális szimbólumnak tekintjük, míg az összes többi karaktert terminálisnak.

  1. A CF nyelvtant a Nyelvtan osztállyal reprezentáljuk, amely kezdőszimbólumot a kezdovaltozo konstruktor argumentumban kapja meg. Egészítsük ki az add_szabaly metódust úgy, hogy a megadott bal és jobb oldalú levezetési szabályt hozzávegye a nyelvtan szabályaihoz. Ha szükséges, módosítsuk az __init__ konstruktort úgy, hogy létrehozza a szabályok tárolására alkalmas adatstruktúrát.
  2. A levezet metódus a paraméterül kapott szó egy bal-levezetését adja vissza egy listában. Ha biztosan nincs ilyen, akkor a False értékkel tér vissza. Ehhez segítségül hívja az előző feladatban bemutatott szélességi keresést, amit a _szelessegi_kereses privát metódus valósít meg. Mivel a gráf most nem véges, nem állíthatjuk elő az éllistáját. Ehelyett a _rakovetkezo metódust használjuk, ami egy adott csucs sztringhez előállítja az onnan kimenő élen elérhető csúcsait a gráfnak.

     Egészítsük ki a _rakovetkezo metódust úgy, hogy a paraméterül kapott csucs sztringből megengedett bal-levezetési lépéssel kapható szavak listáját adja vissza! Például, ha a nyelvtan

     \begin{equation*} S \to aSB \mid bSA \mid \epsilon, \quad A \to aA \mid \epsilon, \quad B \to bB \mid \epsilon, \end{equation*}

     akkor

     self._rakovetkezo('aSbbB') == ['aaSBbbB', 'abSAbbB', 'abbB']
     	

  3. Próbáljuk ki a programot, és keressünk levezetést néhány általunk választott szóhoz! A program után """-típusú megjegyzésben válaszoljunk a következő kérdésekre! (1) Milyen nyelvet határoz meg a cf_hu.py fájlban megadott nyelvtan? (2) Mi történik, ha olyan szót adunk meg a programnak, ami nincs benne a nyelvben? (3) Nem kötelező: A kód milyen megváltoztatásával kezelhető ez az eset? Valósítsuk meg (de csak akkor, ha a program már megbízhatóan működik)!
• A megoldásban segíthet az isinstance() függvény, és az islower(), extend(), append() metódus.