Formális nyelvek gyakorlat, 2005 ősz

7. csoport: kedd, 15:15 -- 16:45, IB.139
14. csoport: csütörtök, R.508, 10:15 -- 12:00

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!

Hirdetmények

Ötödik kis ZH eredményei elérhetőek innen a csoport sorszámára kattintva.

Negyedik kis ZH eredményei elérhetőek innen a csoport sorszámára kattintva.

December 13 és 15, a gyakorlatok első 15 perce: ötödik kis ZH az egész anyagból. Gyakorlásnak javaslom az 5-ik kis ZH-t 2000-ből megoldásokkal.

December 6 és 9, a gyakorlatok első 15 perce: negyedik kis ZH, LL(k)-ig bármi.

Harmadik kis ZH eredményei elérhetőek innen a csoport sorszámára kattintva. Elnézést a sok késésért.

Konzultáció a nagyZH-hoz. Kedden a gyakorlat után, tehát november 8., 17:00- az IB.139-es teremben. A csütörtökiek részére a most következő november 3-i gyakorlat lesz a konzultáció, illetve gyakorlás. A két csoportból bárki bármelyikre jöhet, ahogyan kedve tartja.

Második kis ZH eredményei elérhetőek innen a csoport sorszámára kattintva.

Csütörtöki órák új helyszíne az R.508-as terem.

Október 25 és 27, a gyakorlatok első 15 perce: második kis ZH. A reguláris nyelvek + CF eleje.

Első kis ZH eredményei elérhetőek innen a csoport sorszámára kattintva.

Október 5, szerda, 15:15-16:45, IB134: pótóra a csütörtöki csoportnak.

Október 11 és 13, a gyakorlatok első 15 perce: első kis ZH. A reguláris nyelvekről az első három gyakorlaton elhangzott anyagból.

Gyakorlatok anyaga

Gyakorlat dátumaGyakorlat témájaFeladatsorok, készítette Laczay Bálint és Salamon Gábor Kapcsolódó anyagok Csima Judittól, Varró Gergőtől Vaszil Györgytől
1. 2005. 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; generatív nyelvek számossága megszámlálható [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); generatív nyelvek számossága, részletesen
2. 2005. szeptember 20-22. 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]
3. 2005. szeptember 27-29. Minimálautomata, reguláris nyelvek zártsága a tranzitív lezárt és a konkatenálás műveletére. Epszilon-mentesítés automata konstruálása az eredményként kapott nyelvre. [ps] [ps.zip] [pdf] Megoldás a 8. feladathoz. 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. 2005. október 4-6. További nyelvi műveletek: unió, metszet, komplementer (nézz utána az előadás anyagában). Reguláris kifejezések. Pumpálási lemma, pumpálási lemma részsorozatokra(utóbbihoz ld. a segédanyagot). [ps] [ps.zip] [pdf] Csütörtökiek részére órai jegyzet Fancsik Pétertől 1, 2, 3. Egy kidolgozott feladat véges automata készítéséről metszethez és unióhoz. Példák reguláris kifejezés készítésére automatából: egy régi feladatsor és megoldások a 4.a és a 4.b feladatokhoz. Pumpálási lemma részsorozatokra is, formálisan, bizonyítással. Mit kell tudni reguláris nyelvekről? (Idén kétirányú véges automata nem volt!)
5. 2005. október 11-13. CF nyelvtanok jól fésült alakra hozása (epszilon mentesítés, egyszeres szabályok, felesleges szimbólumok.) Chomsky-féle normálforma, Greibach-féle normálforma. [ps] [ps.zip] [pdf] Segédanyagok CNF-hez és GNF-hez.
6. 2005. október 18-20. Egyértelműség, SaSb, aritmetikai kifejezéseket generáló nyelvtan átalakítása. [ps] [ps.zip] [pdf] SaSb nyelvtan által generált nyelv és egyértelműsége röviden, precízen és világosan.
7. 2005. október 25 és 27. Veremautomaták, CF nyelvtan -> veremautomata (bal- és jobblevezetést megvalósító automata is) [ps] [ps.zip] [pdf] 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!)
2005. november 3 és 8. Gyakorlás a nagyZH-ra. régi ZH feladatok
8. 2005. november 10 és 15. Véges fordító, veremfordító, 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]
9. 2005. november 17 és 22. Á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 (nem egyértelműségről és elutasításról az órán nem volt szó, nézzetek utána, pl. a webes segédanyagoknál). [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
10. 2005. november 24 és 29. LL(k) elemzés, faktorizáció, balrekurzió megszűntetése, erős és gyenge LL(k), erős és gyenge műlödése közti különbség (erről órán már nem volt szó, nézzétek meg pl. a harmadik webes segédanyagot). [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. 2005. december 1 és 6. LR(1) és LR(0) elemzés. [ps] [ps.zip] [pdf] Feladatok megoldással és sok-sok magyarázattal: LR(1); LR(0)
12. 2005. december 6 és 8. erős precedencia elemző, gyenge precedencia elemző, operátor precedencia elemző [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.

További hasznos linkek

Tárgy honlapja követelmények, hirdermények, zh eredmények, fony linkek (feladatok, segédanyagok)