Tárgy: PMB1203L Formális nyelvek és automaták

Oktató: dr. Vályi Sándor

Meghirdetés féléve : 1

Kreditpont : 5

Heti kontakt óraszám (elm.+gyak.): 7+8 levelezőn

Félévi követelmény: kollokvium (szóbeli)

Előfeltétel (tantárgyi kód) : --

Évközi követelmények, vizsgára bocsájtás feltételei: levelezőn nincsenek, mindenki mehet vizsgázni, aki felvette a kurzust. A vizsga tartalamaz gyakorlati feladatokat is. Egy bonyolultabb tárgyköri algoritmus jól dokumentált implementációja modern programozási nyelven előnyt jelent a szóbeli vizsgán.

Tantárgyi program: Formális rendszerek és automaták főbb típusai. Nyelvek, nyelvtanok, normál alakok. Automaták és

nyelvek kapcsolata. Chomsky-féle nyelvosztályok. Műveletek nyelvekkel, nyelvalgebra. Elemzők

és felismerők, nyelvtani algoritmusok. Lindenmayer rendszerek. Néhány fontos nyelvészeti

módszer és eredmény: Kleene tétele, Bar-Hillel lemma, Early-féle algoritmus, közelítő

szövegegyeztetések, Lyon algoritmus. Számítástudományi alkalmazások.

Oktatási segédanyag:

Az előadáson bemutatott prezentációk megtalálhatók a http://moodle.nyf.hu címen.

Kötelező¹ és ajánlott irodalom:

· Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük, Typotex, 2001.
(letölthető prezentáció sűrítményben: http://www.inf.u-szeged.hu/~fulop/oktatas/fonya4_diak.pdf)

· Dömösi Pál et all.: Formális nyelvek és automaták, Debreceni Egyetem, 2003 (http://www.inf.unideb.hu/~domosi.)

· Horváth Géza, Mecsei Zoltán, Nagy Benedek: Gyakorlati összefoglaló, Debreceni Egyetem mobidiák könyvtár.
(http://www.inf.unideb.hu/~domosi.)

· Bach Iván: Formális nyelvek, Typotex, 2001 (letölthető: http://www.typotex.hu/download/formalisnyelvek.pdf)