Nyelvek és automaták

A tantárgy angol neve: Languages and Automata

Adatlap utolsó módosítása: 2018. július 27.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnökinformatikus szak, MSc képzés

Elágazó közös tárgy

 

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZMA04 1,2 3/0/0/f 4  
3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
A tantárgy tanszéki weboldala http://cs.bme.hu/nyau
4. A tantárgy előadója

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

egyetemi docens

Számítástudományi és Információelméleti Tanszék

5. A tantárgy az alábbi témakörök ismeretére épít

Alapvető algoritmusok

6. Előtanulmányi rend
Kötelező:
NEM ( TárgyEredmény( "BMEVISZM104" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZM104", "FELVETEL", AktualisFelev()) > 0)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rendek grafikus formában itt láthatók.

7. A tantárgy célkitűzése

Á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.

8. A tantárgy részletes tematikája

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.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) Heti 3 óra előadás
10. Követelmények

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:

11. Pótlási lehetőségek

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ó.

12. Konzultációs lehetőségek

Hetente adunk ki gyakorló feladatokat, melyeket egy egyeztetett időpontban tartott heti konzultáción az érdeklődőkkel megbeszélünk.

13. Jegyzet, tankönyv, felhasználható irodalom

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.

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra42
Félévközi készülés órákra28
Felkészülés zárthelyire50
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés 
Összesen120
15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Friedl Katalin

egyetemi docens

Számítástudományi és Információelméleti Tanszék