Formális nyelvek és automaták gyakorlat 2010/11 második félév
16. csoport
A gyakorlat célja a formális nyelvek elmélete alapfogalmainak és tételeinek megértetése, elmélyítése, az alkalmazási lehetőségek bemutatása és a „Fordítóprogramok” című tantárgy elméleti előkészítése.
A gyakorlatok két részből állnak, a 45 perces kötelező részből, ahol az új tananyagot és a velük kapcsolatos új feladatokat tárgyaljuk, valamint a 45 perces terembe beosztott konzultációból, ahol a házi feladatok megoldását, illetve a felmerült problémákat tekintjük át. A félév során – előreláthatólag – 13 gyakorlat lesz. Ebből három - március 16., április 20. és május 18. a három zárthelyi időpontja.
A tárgy teljesítése összevont számonkéréssel, a gyakorlati és elméleti rész együttes anyaga alapján történik. A gyakorlati részből 60 pontot (15,15,30), az elméleti részből 40 (egy vizsgazárthelyi) pontot lehet maximálisan elérni. Az osztályzat 50 pontnál elégséges, attól kezdve 10 pontonként eggyel nő. Az osztályzat szükséges feltétele még, hogy a zárthelyik mindegyikében legalább 1/3 pontszámot, míg az elméletiből legalább 10 pontot érjen el valaki.
A
gyakorlati részből 2 minimum feltétel pótlására a szorgalmi időszak első
hetében, május 25-én 16 órakor pótló zárthelyin lesz lehetőség. Az elméleti
részhez tartózó zárthelyi megírására három alkalommal, június 1-én, 8-án és
15-én 16 órakor kerül sor. Ezeken mindaddig részt vehet valaki, amíg legalább
elégséges osztályzatot nem szerez (minden minimum feltétel teljesül és a pontszám
legalább 50).
Aki
a minimumfeltételeket nem teljesíti, a tárgyból nem szerez jegyet. Aki a
minimumfeltételeket teljesíti, de nincs legalább 50 pontja, annak jegye
elégtelen. A tárgyból - tekintettel annak féléves, folyamatos számonkérés
jellegére - utóvizsga nincs (a pótlási lehetőségek vannak helyette - utóvizsga
díjak nélkül).
A gyakorlatok várható anyaga – az előadás menetéhez illeszkedve - a következő:
1. gyakorlat, február 16.:
Célja: A programozási nyelvek szintaxisának leírására használatos eszközök, módszerek bemutatása
Fogalmak, ismeretek: BNF, szabály, levezetés, leírt nyelv, EBNF, BNF kétszintű kiterjesztése, szintaxis-diagram, EP programozási nyelv, Pascal programozási nyelv (a közismert konstrukciók, finom részletek nem).
Feladatok jellege: Egyszerűbb programnyelvi konstrukciók BNF leírása, levezetési példák, BNF átírása EBNF-re, az EP megadása EBNF-el (előre kiadott lapon), programkészítés EP-ben, a PASCAL szintaxis-gráfokon alapuló leírásának áttekintése (előre kiadott lapokon), bizonyos konstrukciók átírása EBNF-re. (Az anyag egy része átvihető a második gyakorlatra)
2. gyakorlat, február 23.:
Célja: A formális nyelvek elmélete alapfogalmainak gyakorlása, formális nyelvek néhány alkalmazási lehetőségének bemutatása (pl. képek reprezentálása a teknőc grafikában, r-áris fák reprezentációja nyelvekkel).
Fogalmak, ismeretek: Ábécé, szó, nyelv, nyelvcsalád, unió, konkatenáció, lezárás, pozitív lezárás, homomorfizmus, opcionálisan párhuzamos kompozíció, teknőc grafika, fák reprezentációja nyelvekkel (opcionálisan a majdnem teljes fák, kiegyensúlyozott fák, Fibonacci fák, binomiális heap).
Feladatok jellege: Egyszerű példák az alapfogalmak gyakorlására, a műveletek és tulajdonságaik bemutatása konkrét példákon keresztül. Koch-szigetek teknőc-grafikával való leírásának tanulmányozása, fák reprezentációja szelektorhalmazukkal, opcionálisan faosztályok leírása nyelveken értelmezett rekurzióval.
3. gyakorlat, március 2.:
Célja: A formális nyelvek elmélete alapfogalmainak elmélyítése, a műveletek gyakorlása.
Fogalmak, ismeretek: Műveletek szavakon, nyelveken, reguláris műveletek, halmazműveletek, megfordítás, homomorfizmus, kezdőszeletek, végszeletek, opcionálisan párhuzamos kompozíció.
Feladatok jellege: A műveletek bemutatása konkrét nyelvekre való alkalmazásukon keresztül, műveletekre vonatkozó azonosságok felismerése, bizonyítása.
4. gyakorlat, március 9.:
Célja: A formális nyelvtan fogalmával való ismerkedés.
Fogalmak, ismeretek: Formális nyelvtan, levezetés (közvetlen, közvetett), generált nyelv. Nyelvtani típusok, nyelvtípusok.
Feladatok jellege: Egyszerű nyelvtanok, példák közvetlen és közvetett levezetésre, levezetésre, illetve a generált nyelvre, az adott nyelvtan típusának meghatározása.
5. gyakorlat, március16.:
1. zárthelyi, 60 perc, 15 pont
Célja: A formális nyelvekkel kapcsolatos alapfogalmak megértésének ellenőrzése.
6. gyakorlat, március 23.:
Célja: Az első zárthelyi tanulságainak levonása. A nyelvtanokkal való nyelvmegadás további gyakorlása, a nyelvtani típusok, illetve a nyelvtípusok fogalmának elmélyítése.
Fogalmak, ismeretek: Nyelv, nyelvtan, generált nyelv, Chomsky-féle nyelvtanosztályozás és nyelvosztályozás, Chomsky-hierarchia (gyenge, erős).
Feladatok jellege:
Nyelvekhez nyelvtan készítése - egyszerűktől a bonyolultabbakig, bemutatva
néhány készítési receptet; nyelvtanokhoz a generált nyelv meghatározása, a
nyelvtan típusának detektálásával. Opcionálisan
1-2 példán a kétirányú tartalmazás bizonyítása.
7. gyakorlat, március 30.:
Célja: A nyelvtanok alapján a generált nyelv felismerése és megadása.
Fogalmak, ismeretek: Nyelv, nyelvtan, generált nyelv, Chomsky-féle nyelvtanosztályozás és nyelvosztályozás, Chomsky-hierarchia (gyenge, erős).
Feladatok jellege: Adott nyelvtan által generált nyelv felismerése, leírása.
8. gyakorlat, március 6.:
Célja: A nyelvtanokon értelmezett transzformációk
gyakorlása, a szóprobléma eldöntése néhány eszközének bemutatása
Fogalmak, ismeretek: Megszorított típusok, normálformák, 2. típusú epszilon-mentesítés, lánc-mentesítés, Chomsky-féle normálformává alakítás, CYK algoritmus, véges, determinisztikus automata.
Feladatok jellege: Konkrét nyelvtanokból kiindulva a konstrukciók tényleges, mechanikus elvégzése. A CYK algoritmus bemutatása példán, néhány véges, determinisztikus automata konstruálása.
9. gyakorlat, március 13.:
2. zárthelyi, 60 perc, 15 pont
Célja: A formális nyelvtanokkal és a szóprobléma eldöntésével kapcsolatos ismeretek megértésének és alkalmazásuk képességének ellenőrzése.
10. gyakorlat, március 27.:
Célja: A véges determinisztikus és nem-determinisztikus automaták (VDA, VNDA) fogalmának gyakorlása és használatuk gyakorlati feladatok megoldására.
Fogalmak, ismeretek: VDA, VNDA, automaták megadási módjai, 3. normálforma, automata-kör, összefüggő automata, mintafelismerés, opcionálisan szótár, lexikális analízis.
Feladatok jellege: Példák automatákra, különböző megadási módokon. Konkrét 3. típusú nyelvtanból indulva normálformára hozás, átírás VNDA-vá, átírás VDA-vá (összefüggő rész). KMP automata egy konkrét mintára, opcionálisan véges nyelvhez lehetőleg kis állapotszámú automata, automata az azonosítókhoz, valós számokhoz, az alapszimbólumok összességéhez.
11. gyakorlat, május 4.:
Célja: A második zárthelyi tanulságainak levonása. A véges automatákra és a harmadik típusú nyelvekre vonatkozó ismeretek elmélyítése, gyakorlati alkalmazása.
Fogalmak, ismeretek: Maradéknyelvek és tulajdonságaik, MYHILL-NERODE tétel, kis Bar-Hillel lemma, reguláris kifejezés, általánosított reguláris kifejezés, Kleene-tétel, automata analízis, minimális automata.
Feladatok jellege: Konkrét nyelvek maradéknyelvei halmazának felírása, ezekből MYHILL-NERODE alapján következtetések levonása. Konkrét nyelvről kis Bar-Hillel lemmával kimutatni, hogy nem reguláris. Néhány reguláris és általánosított reguláris kifejezés felírása. 3 állapotú automata analízise. Automata minimalizáció.
12. gyakorlat, május 11.:
Célja: Az 1 vermekkel és a környezet-független nyelvekkel kapcsolatos alapfeladatok begyakorlása.
Fogalmak, ismeretek: 1 verem, determinisztikus 1 verem, felismert nyelv, szintaxis-fa, legbal és legjobb levezetés, nagy Bar-Hillel lemma, felülről-lefelé és alulról-felfelé elemzés.
Feladatok jellege: 2. típusú nyelvhez nemdeterminisztikus, determinisztikus 1 verem készítése, 1 veremhez 2. típusú nyelvtan előállítása, néhány szintaxis-fa egy konkrét 2. típusú nyelvtanban, legbal, legjobb levezetés előállítása a szintaxisfa alapján. Nagy Bar-Hillel lemma alkalmazása konkrét nyelvre. Kicsit bonyolultabb nyelvtan esetében (adott szóhoz) a felülről-lefelé és az alulról-felfelé elemzés bemutatása.
13. gyakorlat, május 18.:
3. zárthelyi, 90 perc, 30 pontos
Célja: A teljes félévi anyag - ezen belül hangsúlyozottan a 10., 11. és 12. gyakorlat anyaga - elsajátításának ellenőrzése.
A vizsgaidőszak első hete, május 25. 16 óra,:
Pótló zárthelyik
Céljuk: A sikertelen (nem megírt, illetve a minimális 1/3 pontszámot nem elért) zárthelyik pótlása. Mindenki legfeljebb 2 zárthelyi anyagát pótolhatja.