Automaták és formális nyelvek
Az előadás célja, hogy megadja a fordítóprogramok
készítése során használt eszközök elméleti, matematikai jellegű 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.
Azonosító: P-ANY1
Szak: programozó, programtervező matematikus, informatika tanár
Óraszám, kreditszám: 2+2 (informatika tanári szakon a régi tanterv
szerint a gyakorlat opcionális), összesen 4 kredit.
Számonkérés módja: kollokvium, gyakorlati jegy
Előfeltétel: Hivatalosan nincs, de ajánlott a
- Bevezetés a matematikába 3.
félév (vagy azzal egyenértékű tárgy).
Javasolt félév: 4.
Követelmények:
A vizsga alapértelmezésben szóbeli kollokvium, mely a
hallgatósággal történő egyeztetés mellett kiegészülhet az írásbeli vizsgák
lehetőségével is. A kollokviumnak előfeltétele a gyakorlati jegy
megléte (ha ez utóbbi az adott tantervben kötelező).
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.
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).
- 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). A CYK algoritmus.
- 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.
Irodalom:
- J. Demetrovics, J. Denev,
R. Pavlov, A számítástudomány matematikai
alapjai, Tankönyvkiadó, 1995.
- Révész György, Bevezetés a
formális nyelvek elméletébe, Tankönyvkiadó, 1977.
- A. Salomaa, Formal
Languages, Academic Press, 1973.
- Hunyadvári
László, Manhertz Tamás, Formális nyelvek. Elektronikus
előadásjegyzet. Letölthető Hunyadvári László
honlapjáról.