INFORMATIKAI KAR DOKTORI PROGRAM
SZIGORLATI TEMATIKA

Formális nyelvek


A formális nyelvek elméletének alapfogalmai. Formális nyelvtanok és a Chomsky-hierarchia.
Matematikai gépek, mint nyelvfelismerõk. A Chomsky-hierarchiának megfelelõ géphierarchia.
A Chomsky-osztályok és a klasszikus nyelvmûveletek kapcsolata. Az általánosított szekvenciális gépek (transducerek), mint nyelvátalakítók. Nivat tétele. Triók (cone) és absztrakt nyelvcsaládok, a rájuk vonatkozó alapvetõ tételek.
A harmadik típusú nyelvek tulajdonságai (pumpáló-lemma, Kleene tétele, Myhill-Nerode tétele). Harmadik típusú nyelvek jellemzése véges automatákkal, automaták analízise és szintézise, a minimális automata konstrukciója.
A második típusú nyelvek tulajdonságai (normál-formák, pumpáló lemma, Parikh tétele, Shamir tétele, Chomsky-Sczützenberger tétel, a legbonyolultabb környezet-független nyelv, Greibach tétele).
Nyelvi egyenletrendszerek, megoldásuk a minimális fix-pont meghatározásával, az egyértelmû megoldás néhány feltétele. A Gauss-elimináció. A polinomiális és a lineáris egyenletrendszerek, kapcsolatuk a második és harmadik típusú nyelvekkel.
Rekurzívan felsorolható nyelvek, rekurzív nyelvek, kapcsolatuk a Chomsky-hierarchiával. A rekurzívan felsorolható nyelvek reprezentációs tételei. Eldönthetõségi kérdések, Rice tétele.
Nyelvtanok korlátozott levezetésekkel (mátrix-nyelvtanok, programozott nyelvtanok, kontroll-nyelvtanok).
A programozási nyelvek leírásának két továbbfejlesztett eszköze, a kétszintû nyelvtan és az attribútum-nyelvtan.


Irodalom:

Handbook of Formal Languages, Springer-Verlag, Berlin, Heidelberg, New York 1997.
Jozef Gruska (Ed.), Foundation of Computing, International Thomson Computer Press, 1997.
A. Salomaa, Formal Languages, Academic Press, New York, 1973.
J. E. Hopcroft, J. D. Ullman, Fomal Languages and Their Relations to Automata, Addison-Wesley, Reading, Mass., 1969
J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Mass., 1979