Elméleti számítástudomány

(Friedl Katalin, 2026)
  1. Véges automaták (determinisztikus, hiányos, nemdeterminisztikus). Minimalizálás. Pumpálási lemma és alkalmazása.
  2. Veremautomaták (determinisztikus és nemdeterminisztikus). A környezetfüggetlen pumpálási lemma és alkalmazása.
  3. Formális nyelvtanok, Chomsky-hierarchia. A Chomsky-nyelvosztályok és a különböző automata-típusok közötti kapcsolat.
  4. A reguláris nyelvek osztályának és a környezetfüggetlen nyelvek osztályának zártsági tulajdonságai.
  5. Turing-gép és változatai (egy szalagos, több szalagos, nemdeterminisztikus). Church--Turing-tézis. Az R, RE, coRE nyelvosztályok, zártsági tulajdonságaik.
  6. Nevezetes nyelvek és osztályuk: diagonális, univerzális, megállási nyelv, a semmit el nem fogadó Turing-gépek nyelve. Rice-tétel. PCP és Dominó nyelv.
  7. Idő- és tárkorlátos Turing-gépek, idő- és tárosztályok. Tár-idő tétel. A P, NP, coNP, PSPACE és EXPTIME osztályok, ezek kapcsolata egymással és az R osztállyal.
  8. Reguláris és környezetfüggetlen nyelvekkel kapcsolatos kérdések (beletartozás, üresség, végesség, diszjunktság, egyenlőség) algoritmikus bonyolultsága, eldönthetősége.