Formális nyelvek
gyakorlatok Vaszil György csoportjaiban,
2001. őszi félév

Az órák hétfőn 12:15-kor és 14:15-kor kezdődnek az IB - 141-es és IB - 147-es teremben.


A zárthelyikről:

    A gyakorlaton írt kis ZH-k eredményei itt voltak olvashatók.

    Vizsgaidőpontok: december 18. 12 óra, január 9. 11 óra, január 24. 8 óra.

Az egyes órákról:

  1. Szeptember 10.
    Jelölések, nyelvek, generatív nyelvek, bevezető jellegű ismerkedés a grammatikákkal. Megmutattuk, hogy az előadáson (és Bach Iván Formális nyelvek című könyvének a 15. oldalán) szereplő grammatika valóban az { anbncn | n >=1 } nyelvet generálja, valamint szó volt a rögzített ábécé feletti formális nyelvek és generatív nyelvek számosságának különbségéről. (Ezzel kapcsolatban lásd Csima Judit okoskodását).

  2. Szeptember 17.
    A Chomsky féle nyelvosztályok. Determinisztikus és nemdeterminisztkus véges automaták, a nemdeterminisztkus automaták determinisztikussá alakítása. Véges automata alapján 3. tipusú nyelvtan, nyelvtan alapján automata konstruálása. A jobb- és balreguláris nyelvtanok egyenértékűsége Varró Dániel megfogalmazásában.

  3. Szeptember 24.
    Determinisztikus véges automaták minimalizálása. A kétirányban mozgó fejű véges automaták és a hagyományos (csak balról jobbra olvasó) automaták ekvivalenciája, "kétirányú" automata alapján "egyirányú" automata konstruálása okoskodással (gyakran járható út) és általánosan (visszatérési falak és a többi, Csima Judit megfogalmazásában).

  4. Október 1.
    Megbeszéltük, hogy mik is azok a reguláris kifejezések, hogyan jelölhetünk velük reguláris halmazokat, hogyan lehet okoskodással egy nyelvtan vagy egy véges automata alapján reguláris kifejezést konstruálni. Szó volt arról is, hogy hogyan lehet véges automata vagy reguláris nyelvtan alapján felírt egyenletrendszer segítségével reguláris kifejezést kapni.

    A gyakorlat feladatsora. A negyedik feladat (a) pontjának, (b) pontjának, az 5. feladatnak, és a 6. feladatnak a megoldásai is itt vannak.

  5. Október 15.
    Megoldottunk egy véges automata konstruáló példát (egy nyelvre, a négyzetére, a négyzet és a nyelv metszetére valamint a nyelv tranzitív lezártjára), megbeszéltük is kipróbáltuk a pumpálási lemmát, amivel a gyakorlaton befejeztük a reguláris nyelvek témakörét. Feladatok vannak még nálatok, igyekszem majd itt megoldásokat közölni, mindenestre kérek mindenkit, hogy tanulmányozza az eddig tanultakat. A tudnivalók összefoglalása Csima Judit megfogalmazásában.

    Íme egy gyakorló feladat megoldással, még mindig a reguláris témakörből.

    Belefogtunk a környezetfüggetlen nyelvtanok átalakításába is, azaz a törlő szabályok, a láncszabályok és a felesleges (nem termináló és elérhetetlen) szimbólumot tartalmazó szabályok kiküszübölésébe (ha egyszerre többet is el kell végezni, akkor az átalakítások helyes sorrendjére is ügyelni kell).

    gyakorlat feladatsora.

  6. Október 20.
    Megnéztük, hogyan kell környezetfüggetlen nyelvtanokat Chomsky illetve Greibach féle normálformára hozni, ez utóbbi fontos lépése a közvetlen balrekurzió kiküszöbölése. Beszéltünk még a nyelvtanok egyértelműségéről, ezzel kapcsolatban felhívom a figyelmeteket a feladatsor 2. példájára, amiből itt van a b) pont megoldása Csima Judit megfogalmazásában.

    A veremautomatákkal kapcsolatban szó volt arról is, hogy mikor beszélünk determinisztikus, nem-determinisztikus, üres veremmel vagy végállapottal elfogadó automatáról. Az üres veremmel és végállapottal elfogadó veremautomaták egyenértékűségéről itt olvasható egy eszmefuttatás. Végül itt a  3. feladat b) pontjának egy variációja valamint gyakorlásképp egy másik feladat (megoldással) Csima judittól.

    Íme a gyakorlat feladatsora.

  7. Október 29.
    Megoldottuk a múlt órai feladatsor 2. feladatát és a 3. feladat d. pontját (ezekre a múltkor nem maradt idő). Megnéztük és kipróbáltuk a környezetfüggetlen nyelvekre vonatkozó pumpálási lemmát, illetve azt is, hogy hogyan kell nyelvtan alapján veremautomatát konstruálni (ez utóbbi témában egy kidolgozott példa Csima Judittól).

    Figyelmetekbe ajánlom: "cseles" kérdések és válaszok Csima Judit weblapján.

    A feladatsor.

  8. November 5.
    Megbeszéltük mi az a véges fordító és veremfordító. A véges fordító és a fordítandó nyelv alapján konstruáltunk automatát a fordított nyelv elfogadására. Említettük, hogy léteznek szintaxis vezérelt fordítási sémák és beszéltünk arról is, hogy mi az a jellemző nyelv, jellemző nyelvtan.

    A gyakorlat feladatsora.

    Itt a fenti feladatsor 96. számú feladatának megoldása, 97. számú feladatának megoldása és 107. számú feladatának megoldása. (Mind Csima Judit weblapjáról.)

  9. November 12.
    Környezetfüggetlen nyelvek szintaktikai elemzése Cocke-Younger-Kasami (a link mögött Csima Judit szövege) és Earley féle algoritmussal.

    Íme néhány ide kapcsolódó feladat (megoldással) Csima Judit weblapjáról.

  10. November 19.
    LL(k) elemzés. Megbeszéltük hogy néz ki az elemző táblázat, mik azok az erős és gyenge LL(k) nyelvtanok, illetve azt, hogy hogyan lehet a gyenge LL(k) nyelvtanokat a nemterminálisok követő nyelvek szerinti "hasogatásával" LL(k)-vá tenni.

    Íme néhány ide kapcsolódó feladat (megoldással) Csima Judit weblapjáról. A 3. feladatban a "hasogatás" (és a hibajelzeéssel kapcsolatos jelentősége) is megtekintehtő.

  11. November 26.
    LR(k) elemzés. Áttekintettük az LR(0) és LR(1) elemzők konstrukcióját. A "vezérlő" táblázat jegyzetben használatos formáját nem használtuk, kérlek benneteket nézzétek meg.

    Íme Csima Judit tavalyi feladatsora (megoldásokkal). A 3. és az 5. feladatot az órán is megoldottuk.

  12. December 3. és 10.
    A szintaktikai elemzés befejezése, többnyire nélkülem.

Illetve:


Kérdéseiddel fordulj hozzám.