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: 2008. szeptember 1.

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

    Mérnök informatikus szak

    MSc képzés

    Közös tantárgy
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZM104 1 3/0/0/f 4  
    3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin,
    4. A tantárgy előadója Dr. Csima Judit
    5. A tantárgy az alábbi témakörök ismeretére épít Alapvető gráfelméleti ismeretek.
    6. Előtanulmányi rend
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZMA04" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA04", "FELVETEL", AktualisFelev()) > 0)

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

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

    Egyszerű automaták az informatikában sok helyen előfordulnak. A tantárgy bemutatja az alapvető automatatípusokat  és megvizsgálja, melyik típus mire alkalmas. Az automaták vizsgálata szorosan összefonódik a formális nyelvek vizsgálatával is. Cél a klasszikus automaták és a formális nyelvek közötti kapcsolatok 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 bonyolultságát, különös tekintettel a P és NP nyelvosztályokra.


    8. A tantárgy részletes tematikája
    • Véges automaták és reguláris nyelvek (3 hét)

      Determinisztikus és nemdeterminisztikus véges automaták. Véges automaták determinizálása és minimalizálása. Reguláris nyelvtanok és reguláris kifejezések, ezek ekvivalenciája a véges automatákkal. A reguláris nyelvek zártsági tulajdonságai, pumpálás mint a nem regularitás bizonyításának eszköze.

    • Veremautomaták és környezetfüggetlen nyelvek (3 hét)

      Veremautomaták definiciója. Környezetfüggetlen nyelvtanok és nyelvek, normál formák. A környezetfüggetlen nyelvtanok és a veremautomaták kapcsolata. A környezetfüggetlen nyelvek zártsági tulajdonságai, a pumpálás környezetfüggetlen változata. Determinisztikus és nem determinisztikus környezetfüggetlen nyelvek.

    • Turing-gépek, eldönthetőségi kérdések (3 hét)
      Turing-gép definiciója. Eldönthetőség és felismerhetőség (rekurzív, ill. rekurzívan felsorolható nyelvek). Adott nyelvbe tartozás eldöntésének nehézsége. Eldönthetőség reguláris nyelvek és környezetfüggetlen nyelvek esetén, egyszerű elemzési technikák. Egyes fontos nyelvek eldönthetősége.Turing-gépek és a 0. Chomsky nyelvosztály, illetve a lineárisan korlátolt Turing-gépek és a környezetfüggő nyelvek kapcsolata.
    • Az eldönthető nyelvek további osztályozása (2 hét)
    Idő- és tárkorlátos Turing-gépek, a kétféle korlát közötti összefüggések. TIME, SPACE nyelvosztályok és hierarchiájuk. A P, PSPACE, EXPTIME nyelvosztályok.
    • Nemdeterminisztikus Turing-gépek és az NP-teljesség (2 hét)

      Az NP osztály definiciója. Az NP-teljesség fogalma, jelentősége. Alapvető NP-teljes problémák vizsgálata.

    • Kolmogorov-bonyolultság
    A szavak információtartalmának mérése Kolmogorov-bonyolultsággal. 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.
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) előadás
    10. Követelmények A félév során 4 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 négy zárthelyi átlagából adódik.
    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 Az előadóval való egyeztetés szerint.
    13. Jegyzet, tankönyv, felhasználható irodalom
    1. Bach Iván: Formális nyelvek, TypoTex, 2001.
    2. Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTex, 1999.
    3. 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ákra 30
    Felkészülés zárthelyire 48
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása 
    Vizsgafelkészülés 
    Összesen 120
    15. A tantárgy tematikáját kidolgozta dr. Friedl Katalin egyetemi docens, dr. Csima Judit egyetemi adjunktus