Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    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, Számítástudományi és Információelméleti Tanszék
    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