vissza a tantárgylistához   nyomtatható verzió    

    Languages and Automata

    A tantárgy neve magyarul / Name of the subject in Hungarian: Nyelvek és automaták

    Last updated: 2012. november 24.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZM104 1 3/0/0/f 4  
    3. Course coordinator and department Dr. Friedl Katalin,
    6. Pre-requisites
    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ó.

    8. Synopsis Finite automata (deterministic and non-deterministic), regular expressions, regular languages, closure properties, pumping lemma for regular languages. Push-down automata, context-free languages, Chomsky and Greibach normal forms, closure properties, pumping lemma for context-free languages. Turing-machines, recursive and recursively enumerable languages, linear bounded automata. Parsers for context-free languages. Time- and space-complexity: P, PSPACE, EXPTIME language classes. Non-deterministic Turing machines, NP language class, NP completeness, NPcomplete languages. Kolmogorov complexity: incomputability, Kolmogorov randomness.
    14. Required learning hours and assignment
    Kontakt óra
    Félévközi készülés órákra
    Felkészülés zárthelyire
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés
    Összesen