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:
- 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).
- 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.
- 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).
- 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.
- 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).
A gyakorlat feladatsora.
- 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.
- 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.
- 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.)
- 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.
- 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ő.
- 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.
- December 3. és 10.
A szintaktikai elemzés befejezése, többnyire nélkülem.
Illetve:
|