5. csoport: hétfő, IB.142, 14:15 -- 15:45
12. csoport: szerda, IB.142, 15:15 -- 16:45
Ha bármi kérdésed van a tárgyról, feladatokról vagy másról, írj az fd kukac cs.bme.hu címre!
Nézzétek meg a félévi pontszámokat a tárgy honlapján. Ha probléma van, akkor december 17-ig jelezzétek emailben.
| Gyakorlat dátuma | Gyakorlat témája | Feladatsorok, készítette Laczay Bálint és Salamon Gábor | Kapcsolódó anyagok Csima Judittól és Vaszil Györgytől | |
| 1. | 2004. szeptember 13-15. | Nyelv, nyelvtan, generált nyelv, Chomsky-féle nyelvosztályok, készítsünk bal reg./jobb reg./CF nyelvtant egy nyelvhez, mit generál egy adott nyelvtan | [ps] [ps.zip] [pdf] | Chomsky-féle nyelvosztályok pontos és tömör leírása (epszilon szabályok is), aibici-t generáló nyelvtan(az órai 6. feladathoz hasonló probléma megoldással) |
| 2. | 2004. szeptember 20-22. | Generatív nyelvek számossága megszámlálható, véges automata, determinisztikussá alakítás, bal és jobb reguláris nyelvtanokhoz véges automata készítése és viszont | [ps] [ps.zip] [pdf] | Generatív nyelvek számossága, részletesen |
| 3. | 2004. szeptember 27-29. | Minimálautomata, reguláris nyelvek zártsága a tranzitív lezárt és a konkatenálás műveletére, automata konstruálása az eredményként kapott nyelvre | [ps] [ps.zip] [pdf] | Egy feladatsor és egy megoldás a feladatsor 5-ik feladatához. Nagyon ajánlom a konkatenált és a tranzitív lezárt tanulásához. |
| 4. | 2004. október 4-6. | KisZH, eredmények elérhetőek innen. További nyelvi műveletek, unió, metszet, komplementer. Fontos: műveletekkel kapcsolatos átalakítások, epszilon-szabályok megszűntetésének eseteit végig nézni a könyvben. | [ps] [ps.zip] [pdf] | "Segítik a táblára felírtak az anyag megtanulását? Szinte művészien tökéletes." Egy kidolgozott feladat véges automata készítéséről metszethez és unióhoz |
| 5. | 2004. október 11-13. | Véges automatából reguláris kifejezés és vissza. Pumpálási lemma. Levezetési fa, CF nyelvtanok egyértelműsége, posztfix lenyel nyelvtan. | Múlt órai feladatsor vége, következő órai eleje | Mit kell tudni reguláris nyelvekről? (Idén kétirányú véges automata nem volt!) Pumpálási lemma részsorozatokra is, formálisan, bizonyítással. |
| 6. | 2004. október 18,27. | Egyértelműség, SaSb, CF nyelvtanok jól fésült alakra hozása (epszilon mentesítés, egyszeres szabályok, felesleges szimbólumok. Sorrend fontos, mert epszilon mentesítés közben keletkezhet egyszeres szab., és egyszeres szab. szűrése közben keletkezhet felesleges szimbólum.) | [ps] [ps.zip] [pdf] | SaSb nyelvtan által generált nyelv és egyértelműsége röviden, precízen és világosan. |
| 7. | 2004. október 25 és november 3. | Chomsky- és Greibach-féle normál formák, infix aritmetikás nyelvtan átalakítása, veremautomata. | [ps] [ps.zip] [pdf] | CNF, GNF átalakítás általános leírása egy-egy példával Varró Gergőtől. A GNF részt különösen ajánlom mindenkinek. Verem automatás feladatok 1 , 2 megoldással. Egy korábbi ZH és pótZH megoldással. (kétirányú véges automata most nem lesz, CF-nyelvek és veremautmaták viszont lehetnek!) |
| 8. | 2004. november 8-11. | Üres veremmel elfogadó, mélybe látó veremautomata, CF nyelvtanhoz veremautomata bal- és jobblevezetéssel. Véges fordító, verem fordító. Mi a fordított nyelv? Reg. véges fordítottja reg., CF véges fordítottja CF. | [ps] [ps.zip] [pdf] | |
| 9. | 2004. november 15-17. | ZH feladatok, egyszerű szintaszisvezérelt fordítási séma, jellemző és szigorúan jellemző nyelvtan (gyakorlaton nem volt róla szó, nézzetek utána a könyvben). | [ps] [ps.zip] [pdf] | |
| 10. | 2004. november 22-24. | LL(k) elemzés, faktorizáció, balrekurzió megszűntetése, erős LL(k), gyenge LL(k)gyenge és erős elemző műlödése közti különbség | [ps] [ps.zip] [pdf] | Feladatok megoldással: balrekurzió megszűntetése után erős LL(1); gyenge LL(2); gyenge és erős LL(2) különböző műlödése |
| 11. | 2004. november 29, december1. | LR(1) és LR(0) elemzés | [ps] [ps.zip] [pdf] | Feladatok megoldással és sok-sok magyarázattal: LR(1); LR(0) |
| 12. | 2004. december 6,8. | erős precedenciaelemző, gyenge precedenciaelemző, | [ps] [ps.zip] [pdf] | Az 5-ik kis ZH 2000-ből megoldásokkal. Precedencia relációk meghatározása; precendecia elemzős feladat megoldással; operátor precedencia relációk meghatározása; oprátor precedencia elemzős feladat megoldással. |
| 13. | 2004. december 13, 15. | Általános elemzők CF nyelvtanokhoz: Earley-algoritmus, Cocke-Younger-Kasami-algoritmus (CYK). Ezek viselkedése nem egyértelmű nyelvtanokon, elutasítás esetén. Nullás nyelvosztály: mit generál ez a nyelvtan? feladatok. | [ps] [ps.zip] [pdf] | Órai első Earley-feladat megoldása; órai második Earley-feladat megoldása (kézzel írt, 2.5MB); CYK algoritmus leírása; egy CYK feladat megoldással |
Tárgy honlapja követelmények, hirdermények, zh eredmények, fony linkek (feladatok, segédanyagok)
