Course details

# Theoretical Computer Science Seminar

STI Acad. year 2012/2013 Winter semester 2 credits

Guarantor

Language of instruction

Completion

Time span

Assessment points

Department

Lecturer

Subject specific learning outcomes and competences

Generic learning outcomes and competences

Learning objectives

Prerequisite kwnowledge and skills

Study literature

- Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
- Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0-201-44124-1
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997. ISBN 1-85032-243-0

Fundamental literature

- Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc., 1997. ISBN 0-387-94907-0
- Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0-201-44124-1
- Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4
- Brookshear, J.G.: Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7
- Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8

Syllabus of lectures

- Sets and relations. Strings, languages, and operations over them. Grammars, the Chomsky hierarchy of grammars and languages.
- Regular languages and finite-state automata (FSA), determinization and minimization of FSA, conversion of regular expressions to FSA.
- Kleene algebra. Pumping lemma, proofs of non-regularity of languages.
- Context-free languages and grammars. Transformations of context-free grammars.
- Operations on context-free languages and their closure properties. Pumping lemma for context-free languages.
- Push-down automata, (nondeterministic) top-down and bottom-up syntax analysis. Deterministic push-down languages.
- Turing machines.
- Recursive and recursively enumerable languages and their properties.
- Decidability, semi-decidability, and undecidability of problems, reductions of problems.
- Computable functions. Other Turing-complete computing mechanisms (automata with multiple push-down stacks, counter automata).
- Complexity classes. Properties of space and time complexity classes.
- NP problems. Polynomial reduction.
- Applications of results of theoretical computer science in compilers, automated verification, linguistics, etc. An overview of various areas extending the discussed subjects (automated learning of languages from patterns, tree languages with applications in verification or in XML manipulations, counter automata with constraints, hierarchies of undecidable problems, ...).

Controlled instruction

Exam prerequisites

Course inclusion in study plans