Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
Nyelvek és automaták
A tantárgy angol neve: Languages and Automata
Adatlap utolsó módosítása: 2018. július 27.
Mérnökinformatikus szak, MSc képzés
Elágazó közös tárgy
Név:
Beosztás:
Tanszék, Int.:
Dr. Csima Judit
egyetemi docens
Számítástudományi és Információelméleti Tanszék
Dr. Friedl Katalin
Alapvető algoritmusok
A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.
A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.
Áttekintve az alapvető automatatípusokat, a félév során megvizsgáljuk, melyik típus mire alkalmas. Az automaták vizsgálata szorosan összefonódik a formális nyelvek vizsgálatával. Cél a klasszikus automaták és a formális nyelvek közötti kapcsolatok mélyebb leírása. A hallgatók megismerik a fordítóprogramok készítése során használható elméleti alapokat is. A Turing-gépek kapcsán megvizsgáljuk egyes elméleti és gyakorlati problémák és nyelvek algoritmikus eldönthetőségének kérdését.
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.
A félév során 2 zárthelyit iratunk. A félév teljesítésének feltétele: minden zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a zárthelyik átlagából adódik.
A vizsgaidőszakban: --
Elővizsga:
A szorgalmi időszak során minden zárthelyi dolgozathoz lesz pótlási (javítási) lehetőség.
A pótlási héten egyetlen alkalom lesz amikor egy tetszőleges zh dolgozat pótolható.
Hetente adunk ki gyakorló feladatokat, melyeket egy egyeztetett időpontban tartott heti konzultáción az érdeklődőkkel megbeszélünk.
Csima Judit, Friedl Katalin: Nyelvek és automaták, elektronikus jegyzet.
Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTex, 1999.
Michael Sipser: Introduction to the theory of computation, Thomson Course Techn., 2006.
