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: 2024. február 17.

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

    Common Subject 
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZMA12   3/0/0/f 5  
    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. KatalinFriedl, associate professor, Department of Computer Science and Information Theory

    László Kabódi, teaching assitant, Department of Computer Science and Information Theory

    Dr. Gyula Katona, associate professor, Department of Computer Science and Information Theory
    5. Required knowledge Basic knowledge of graphs, complexity classes P and NP
    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ó.

    7. Objectives, learning outcomes and obtained knowledge
    The course covers the most important types of automaton and the basics of formal grammar. It introduces the relationships between automata and grammars and the limits of their applicability. Students will be introduced to the main theoretical foundations necessary for the construction of translation programs. In the context of Turing machines, they will also learn about problems that are undecidable and indecidable in algorithms. 

    (1) Familiarisation with the automata and grammars discussed, illustrated by examples. 

    (2) Understanding the relationships between different automata and grammars. 

    (3) Applying the techniques learned. 

    (4) The ability to select and apply the appropriate tool for a given problem.
    8. Synopsis
    1. Concepts of alphabet, word and language. Deterministic finite automaton. Class of regular languages and their closure properties to 
    union, intersection, difference, complement.

    2. Incomplete, nondeterministic and epsilon-transiton finite automata, their equivalence. 
    The class of regular languages is closed to concatenation and transitive closure.

    3. Equivalence relation on words and states of a finite automaton, their relation. Minimal automata.

    4. Regular expressions, their equivalence with finite automata. Proof of non-regularity, the pumping lemma.

    5. Formal grammars, the Chomsky hierarchy. Regular grammars. 
    Decision questions about regular languages (empty, finite, does it contain the given word, are two languages equal).

    6. Context-free grammars and languages. Simplification of CF grammars: Epsilon rules, chain rules, elimination of redundant symbols.

    7. Closure properties of context-free languages. Non context-free languages, the pumping lemma.

    8. Non-deterministic and deterministic stack automata. CF grammar and stack automata. Deterministic CF languages.

    9. Deciding inclusion: Cocke-Younger-Kasami algorithm and its efficiency. General 
    analysts.

    10. Ambiguity of CF grammars and languages, examples, relation to determinism. 

    11. Deterministic and non-deterministic Turing machines. Determinization of non-deterministic Turing machines. 

    12. Definition of R and RE classes, examples. The Church-Turing thesis. 

    13. Equivalence of single and multitape Turing machines. Famous languages: diagonal, universal, halting language. 

    14. Closure properties of R and RE. Relationship between R, RE, coRE, further examples. 

    15. Rice's theorem and its applications. Post correspondence problem.

    16. Algorithmic quiestions in CF grammars: decidable and undecidable problems.

    17. Generative languages and Turing machines, context-sensitive  languages and the relation to linearly constrained Turing machines.

    18. Space- and time-bounded Turing machines. Space-time theorem. TIME, SPACE, NTIME NSPACE classes. Their closure properties, and relationship. 

    19. Relation of P, NP, PSPACE, EXPTIME classes.  Witness theorem for the class NP. Karp reduction, Cook-Levin theorem 
    on NP-completeness of SAT.  Other NP-complete languages

    20. Relation of Turing machines to the RAM model, Relation between time bounds.

    21. Repetition, Reserve.
    9. Method of instruction
    Lecture, but some of the details (proofs) must be learnt independently from the notes provided.  

    Weekly practice exercises (not to be handed in) to help learning and check understanding.
    10. Assessment Two tests during the semester. For a passing grade one has to achieve at least 40% on each. 
    11. Recaps There is a retake for both tests.
    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
    Contact classes42
    Preparation for classes28
    Preparation for tests50
    Reading assignment30
    Total150
    15. Syllabus prepared by Dr. Katalin Friedl, associate professor, Department of Computer Science and Information Theory