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ó    

    Languages and Automata

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

    Last updated: 2020. július 9.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZMA04 1,2 3/0/0/f 4  
    3. Course coordinator and department Dr. Friedl Katalin,
    Web page of the course cs.bme.hu/la
    4. Instructors

    Dr Judit Csima, associate professor, Department of Computer Science and Information Theory

    Dr Katalin  Friedl associate professor, Department of Computer Science and Information Theory 

    László Kabódi, associate lecturer, Department of Computer Science and Information Theory 

    5. Required knowledge Basic algorithms
    6. Pre-requisites
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZM104" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZM104", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZMA12", "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA12", "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. Objectives, learning outcomes and obtained knowledge 
    To learn the basics of the theory of automata, the abstract definition, mathematical  properties. To learn about formal languages and their connection to automata. To learn about the computational and practical consequences of Turing-machines. Emphasis is on theory  and mathematical proofs.
    8. Synopsis

    Deterministic finite automaton (DFA)

    Regular languages, their properties. 

    Nondeterministic finite automaton (NFA), algorithm to convert it to DFA

    Minimal DFA construction. Regular expressions and their connection to NFA

    The existence of non-regular languages, pumping lemma 

    Formal grammars, Chomsky hierarchy. Regular grammars 

    Algorithm to construct NFA from regular grammar, and regular grammar from NFA. Context free 8CF9 grammars and languages, parse trees, ambiguous words, grammars, and languages.

    Standardization of CF grammars:  algorithms to remove epsilon rules, unit rules, unneeded symbols

    Chomsky normal form. Closure properties of CF languages

    The existence of non CF languages. Pumping lemma for CF languages

    Closure properties of CF languages. A simple parser: Cocke-Younger-Kasami algorithm. Pushdown automata (PDA)

    Equivalence of PDA and CF grammars

    Turing machine variations (one tape/multitape, deterministic/non-deterministic), their equivalence

    Universal Turing machine. The notion of recursive (decidable) languages and recursively enumerable (recognizable) languages, examples. Diagonal language, universal language, halting problem.

    The language classes R, RE, coRE, their connections, closure properties  

     The complement of the diagonal language. Theorem of Rice

    Post correspondence problem.  Time complexity and space complexity of languages

     

     

     

    9. Method of instruction 3 hours lecture per week
    10. Assessment Two tests during the semester. For a passing grade one has to achieve at least 40% on each. 
    11. Recaps There are three retake occasions: one for each tests, and at the end of the semester a third when either one (but only one) can be  taken.
    12. Consultations By appointment
    13. References, textbooks and resources Michael Sipser: Introduction to the theory of computation, Thomson Course Techn., 2006.
    14. Required learning hours and assignment
    Kontakt óra42
    Félévközi készülés órákra42
    Felkészülés zárthelyire36
    Házi feladat elkészítése
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés
    Összesen120
    15. Syllabus prepared by Dr Katalin  Friedl associate professor, Department of Computer Science and Information Theory