Formális nyelvek
Az előadás célja,
hogy megalapozza egyrészt a magasabb szintű számításelméleti
tanulmányokat, megadja másrészt bizonyos gyakorlati feladatok (természetes
nyelvek feldolgozása, természetes nyelvek gépi fordítása, programozási nyelvek
fordítása és értelmezése) megoldása során használt eszközök elméleti hátterét.
Bevezetésre kerülnek a szintaxis leírásra használatos legfontosabb eszközök
(BNF, szintaxis diagram). Kifejlesztésre kerülnek azok a matematikai eszközök,
melyekkel a szintaxis elemzés témaköre absztrakt szinten tárgyalható (formális
nyelvtanok, absztrakt matematikai gépek). Az előadás a legfontosabb
elemzési módszerek bemutatásával zárul.
Kurzuskód: IP-08aFNYE, IP-08bFNYE, IP-08cFNYE, IP-08eFNYE
Szak: Programtervező informatikus BSc
Óraszám: 2 óra előadás +
2 óra gyakorlat
Kreditszám: 2+2, összesen 4
kredit
Számonkérés módja: kollokvium, gyakorlati jegy
Előfeltétel: Diszkrét matematika 1 teljes elvégzése (gyakorlati
jegy + kollokvium)
Az ajánlott tanterv szerinti félév: a tanulmányok 2. féléve (de mivel a páratlan
félévekben is indul keresztfélévként, ezért minden félévben felvehető)
Követelmények:
A gyakorlati jegy feltétele a zárthelyi dolgozatok mindegyikéből
legalább az elégséges minősítés megszerzése. A zárthelyik száma legalább
kettő, tényleges számukat és a gyakorlati jegy meghatározásának konkrét
feltételeit a gyakorlatvezetők határozzák meg.
A kollokvium írásbeli, félévenként 2 ismétlési lehetőséggel.
Az esti tagozaton az óraszámok és a követelmények ettől kissé
eltérhetnek.
Tematika
- A formális nyelvek
elméletének tárgya és történeti előzményei. A formális nyelvek
elméletének alapfogalmai (ábécék, szavak, nyelvek, nyelvcsaládok).
Műveletek szavakon és nyelveken. Nyelvek megadásának konstruktív
módszerei (listázás, logikai formulák igazsághalmaza, strukturális
rekurzió, eldöntő algoritmus, felsoroló algoritmus, matematikai gép,
formális nyelvtan).
- Formális nyelvtanok,
példák, bizonyítási módszerek, nyelvtanok alaptípusai, megszorítások,
normálformák és egyenértékűségi tételek (a 2. és 3. típus esetén a
bizonyításhoz szükséges konstrukciókkal). Chomsky-féle hierarchiák. A
nyelvtannal való leírás korlátjai és a Church – tézis.
- A Chomsky-féle
nyelvosztályok és a reguláris nyelvi műveletek kapcsolata.
- A szóprobléma eldöntése a
nyelvtannal leírható nyelvek esetében (parciális rekurzivitás,
rekurzivitás, polinom idejű eldöntés, lineáris idejű eldöntés).
A CYK algoritmus.
- Véges automaták
(determinisztikus, nemdeterminisztikus változat, epszilon átmenetes
változat), példák. A különböző változatok felismerő erejére
vonatkozó tételek, kapcsolatuk a Chomsky-féle hierarchiával.
- A 3. típusú nyelvek
tulajdonságai (Kis Bar-Hillel lemma, Kleene tétele, Myhill-Nerode tétele).
- Véges automaták
alkalmazásai - lexikális elemző, mintafelismerő, szótárak
leírása, általánosított reguláris kifejezések böngészőkben.
- Minimális automaták
(definíciók, egyértelműség, konstrukciók).
- Véges determinisztikus
automaták szintézise és analízise.
- A szóprobléma eldöntése 2.
típusú nyelveken veremautomatával (veremautomaták definíciója, példák, a
felismerő erejükre vonatkozó tételek). 2. típusú nyelvek
tulajdonságai (jellemzésük szintaxis fákkal, egyértelműségi kérdések,
nagy Bar-Hillel lemma és alkalmazásai). A 2. típus hatóerejének
kiterjesztése – attribútum nyelvtanok, kétszintű nyelvtanok.
- 2. típusú nyelvtanok
szintaktikus elemzése, az alapvető elemzési stratégiák, speciális
nyelvtanok (LL, LR).
Irodalom magyar
nyelven:
- Révész György, Bevezetés a
formális nyelvek elméletébe, Tankönyvkiadó, 1977.
- J. Demetrovics, J. Denev,
R. Pavlov, A számítástudomány matematikai
alapjai, Tankönyvkiadó, 1995.
- Hunyadvári
László, Manhertz Tamás, Formális nyelvek,
Elektronikus előadásjegyzet 1995. (Letölthető Hunyadvári László honlapjáról).
- Dr. Fülöp Zoltán, Formális nyelvek és szintaktikus elemzésük, Polygon,
Szeged, 1999, 2. kiadás: Polygon, Szeged, 2004.
- Bach Iván,
Formális nyelvek, Typotex, 2001. ISBN 9639132
Ajánlott még:
- A. Salomaa,
Formal Languages, Academic Press, 1973.