Nyelvek és automaták

1) Véges automaták, reguláris nyelvek  átismétlése. Minimálautomata. Véges automaták megfeleltetése a reguláris kifejezésekkel A reguláris nyelvek zártsági tulajdonságai: halmazműveletek, konkatenálás, tranzitív lezárt.  

2) A reguláris pumpálási lemma és alkalmazása. Példák reguláris és nem reguláris nyelvekre. Chomsky-féle nyelvosztályok. Reguláris nyelvtanok és reguláris nyelvek kapcsolata. Veremautomaták, környezetfüggetlen nyelvek és nyelvtanok (ismétlés). Üres veremmel elfogadó veremautomata. 

3) Környezetfüggetlen nyelvtanok átalakításai, normálformák. A környezetfüggetlen nyelvek zártsági tulajdonságai. A pumpálás környezetfüggetlen változatai, (pumpálási és Ogden-lemma) alkalmazásuk, példák.

4) Determinisztikus és nem determinisztikus környezetfüggetlen nyelvek fogalma. A veremautomaták nem determinizálhatók. Algoritmikus kérdések: üresség, különbözőség reguláris és környezetfüggetlen esetben. Az elemző feladata: a beletartozás eldöntése.

5) Cocke-Younger-Kasami-algoritmus. Általános elemzői módszerek. Kimenettel rendelkező automaták. Melay-, Moore-automaták, Véges fordítók. A reguláris nyelvek zártsága a véges fordításra. Veremfordító és szintakszisvezérelt fordítási séma.

6) A Turing-gép definíciója, a különféle definíciók ekvivalenciája (több szalagos, nemdeterminisztikus). Eldönthetőség és felismerhetőség (rekurzív, ill. rekurzívan felsorolható nyelvek). Számoló Turing-gép.

7) Church-Turing-tézis. Univerzális Turing-gép létezése.  A diagonális nyelv nem rekurzívan felsorolható. Az univerzális nyelv és megállási nyelv rekurzívan felsorolható, de  nem rekurzív.

8) Az R osztály zárt a műveltekre, az  RE osztály a komplementerképzés kivételével zárt. Komplementer nyelvosztályok. R a RE és coRE  metszete. További nem eldönthető nyelvek: Church-tétel, üres nyelv.

9) A nemtriviális nyelvi tulajdonságok eldönthetetlensége: Rice-tétel. Ennek alkalmazásai. Dominóprobléma. Post megfeleltetési problémája, és alkalmazása CF-nyelvekkel kapcsolatos kérdések eldönthetetlenségének bizonyítására.

10) Az 1. Chomsky-féle nyelvosztály, a két definíció egyenértékűsége. A 0. Chomsky-féle nyelvosztály és az RE kapcsolata.

11) Időigény és tárigény, idő- és tárkorlátos Turing-gépek.  A tár-idő tétel. TIME és SPACE osztályok zártsága a műveletekre. Nemdeterminisztikus idő és tárigény.  A  P, NP, coNP, PSPACE, EXPTIME osztályok, kapcsolatuk.

12) Egy reálisabb számítási modell a RAM-gép. A RAM-gép és a Turing-gép egyenértékűsége, idő- és tárbonyolultságuk kapcsolata.

13)  Kolmogorov-bonyolultság fogalma.  Algoritmikus tömörítés és a Kolmogorov-bonyolultság. Kapcsolat a véletlenszerűséggel. Az optimális tömörítés mértékének eldönthetetlensége.

14) Ismétlés, összefoglalás, tartalék.