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: 2023. január 12.

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

    Mérnökinformatikus MSc

    Közös tantárgy

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZMA12   3/0/0/f 5  
    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

    Dr. Csima Judit,      egyetemi docens, SZIT 

    Dr. Friedl Katalin,   egyetemi docens, SZIT 

    Kabódi László,        egyetemi tanársegéd, SZIT 

    Dr. Katona Gyula,   egyetemi docens, SZIT
    5. A tantárgy az alábbi témakörök ismeretére épít

    Alapvető gráfelméleti ismeretek, a P és NP bonyolultsági osztályok.

    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

    A tantárgy a legfontosabb automatatípusokkal, és a formális nyelvtanok alapjaival foglalkozik. Bemutatja az automaták és nyelvtanok közötti kapcsolatokat,   alkalmazhatóságuk határait. A hallgatók megismerkednek a fordítóprogamok készítéséhez szükséges legfontosabb elméleti alapokkal. A Turing-gépek kapcsán megismerkednek algorimussal eldönthetetlen és hatékonyan nem eldönthető problémákkal is. 

    (1)  A tárgyalt  automaták és nyelvtanok megismerése, példákon szemléltetése. 

    (2)  A különböző automaták és nyelvtanok közötti kapcsolatok átlátása. 

    (3)   A tanult technikák alkalmazása. 

    (4)  Adott problémához a megfelelő eszköz kiválasztása, alkalmazásának képessége.

    8. A tantárgy részletes tematikája
    1. Ábécé, szó, nyelv fogalma. Determinisztikus véges automata. Reguláris nyelvek osztálya, és ennek zártsága unióra, metszetre, különbségre, komplementerre.
    2. Hiányos, nemdeterminisztikus és epszilon-átmenetes véges automata, ezek ekvivalenciája. A reguláris nyelvek osztálya zárt az összefűzésre és tranzitív lezárásra.
    3. Ekvivalenciareláció szavakon és egy véges automata állapotain, ezek kapcsolata. Minimálautomata.
    4. Reguláris kifejezések, ekvivalenciájuk a véges automatákkal. Nem regularitás bizonyítása, a pumpálási lemma.
    5. Formális nyelvtanok, a Chomsky hierarchia. Reguláris nyelvtanok. Reguláris nyelvekkel kapcsolatos eldöntési kérdések (üres, véges, tartalmazza-e az adott szót, egyenlő-e két nyelv)
    6. Környezetfüggetlen nyelvtanok és nyelvek. CF nyelvtanok egyszerűsítése: epszilon-szabályok, láncszabályok, felesleges szimbólumok kiküszöbölése.
    7. Környezetfüggetlen nyelvek zártsági tulajdonságai. Nem környezetfüggetlen nyelvek, a pumpálási lemma.
    8. Nemdeterminisztkus és determinisztikus veremautomata. CF nyelvtan és veremautomata kapcsolata. Determinisztikus CF nyelvek.
    9. A beletartozás eldöntése:  Cocke-Younger-Kasami-algoritmus és ennek hatékonysága. Általános elemzők.
    10. CF nyelvtanok és nyelvek egyértelműsége, példák, kapcsolat a determinisztikussággal. 
    11. Determinisztikus és nemdeterminisztikus Turing-gépek. Nemdeterminisztikus Turing-gépek determinizálása. 
    12. Az R és RE osztályok fogalma, példák. A Church-Turing-tézis. 
    13. Egy- és többszalagos Turing-gépek ekvivalenciája. Nevezetes nyelvek: diagonális, univerzális, megállási nyelv. 
    14. Az R és RE zártsági tulajdonságai. R, RE, coRE kapcsolata, további példák. 
    15. Rice-tétel és alkalmazásai. Post megfeleltetési problémája.
    16. Algoritmikus kérdések a CF nyelvtanokkal kapcsolatban: eldönthető és  eldönthetetlen problémák.
    17. Generatív nyelvek és Turing-gépek, környezetfüggő nyelvek és a lineárisan korlátozott Turing-gépek kapcsolata.
    18. Tár- és időkorlátos Turing-gépek. Tár-idő tétel. TIME, SPACE, NTIME NSPACE osztályok. Zártsági tulajdonságaik,  kapcsolatuk. 
    19. A P, NP, PSPACE, EXPTIME osztályok kapcsolata.  Tanú tétel az NP osztályra. Karp-redukció, Cook-Levin tétel a SAT NP-teljességéről.  További NP-teljes nyelvek. 
    20. Turing-gépek kapcsolata a RAM modellel, Kapcsolat az időkorlátok között.
    21. Ismétlés, tartalék.
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    Előadás, de néhány részletet (bizonyítást) a kiadott jegyzetből önállóan kell elsajátítani 

    Hetente a tanulást segítő, a megértést ellenőrző gyakorló feladatsor (nem kell beadni).

    10. Követelmények 2 zárthelyi, mindkettőn legalább 40%-ot kell elérni. A végső jegy a két zh átlagából adódik.
    11. Pótlási lehetőségek

    Mindkét zh-hoz 1-1 pótzh lesz, melyen az adott zh-t pótolni vagy javítani lehet. (A pótzh felülírja az eredeti zh eredményét.)

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

    Az előadóval való egyeztetés szerint.

    13. Jegyzet, tankönyv, felhasználható irodalom
    • Csima Judit, Friedl Katalin: Nyelvek és automaták, elektronikus jegyzet, elérhető a tantárgy honlapjáról. 
    • 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ása30
    Vizsgafelkészülés 
    Összesen150
    15. A tantárgy tematikáját kidolgozta

    Dr Friedl Katalin, egyetemi docens, SZIT