Title:  Theoretical Computer Science Seminar 

Code:  STI 

Ac.Year:  2009/2010 

Term:  Winter 

Study plans:  

Language:  Czech 

Credits:  2 

Completion:  accreditation 

Type of instruction:  Hour/sem  Lectures  Sem. Exercises  Lab. exercises  Comp. exercises  Other 

Hours:  0  26  0  0  0 

 Examination  Tests  Exercises  Laboratories  Other 

Points:  0  0  0  0  0 



Guarantee:  Vojnar Tomáš, prof. Ing., Ph.D., DITS 

Lecturer:  Vojnar Tomáš, prof. Ing., Ph.D., DITS 
Faculty:  Faculty of Information Technology BUT 

Department:  Department of Intelligent Systems FIT BUT 

 Learning objectives: 

To broaden student abilities to apply advanced knowledge from the theory of formal languages and automata as well as the theory of computability and complexity, and abilities to solve concrete theoretical as well as practical problems from the given area.  Description: 

The course has a form of practical demonstration exercises with an active participation of the students in solving various concrete problems from the areas of the theory of formal languages and automata as well as the theory of computability and complexity. The examples being solved fall into the areas of advanced theory and applications of regular languages, contextfree and context languages, Turing machines, decidability, reductions of decidability problems, computable functions, and basics of complexity. The application areas include modeling of systems, formal analysis and verification, compilers, artificial intelligence, linguistics, etc.  Knowledge and skills required for the course: 

Basic knowledge of the theory of algebra, graphs, as well as regular and contextfree languages.  Subject specific learning outcomes and competences: 

A deeper understanding and an ability to apply knowledge from the theory of formal languages and the theory of computability and complexity. A student is able to apply the acquired knowledge when solving theoretical as well as practical problems in modeling of systems, programming, formal specification, design automation, verification, and/or artificial intelligence.  Generic learning outcomes and competences: 

Broader and deeper abilities to formalize and solve problems of computer science as well as engineering, design algorithms as well as construct proofs. A student also acquires better abilities for research in various areas of computer science.  Syllabus of lectures: 

 Sets and relations. Strings, languages, and operations over them. Grammars, the Chomsky hierarchy of grammars and languages.
 Regular languages and finitestate automata (FSA), determinization and minimization of FSA, conversion of regular expressions to FSA.
 Kleene algebra. Pumping lemma, proofs of nonregularity of languages.
 Contextfree languages and grammars. Transformations of contextfree grammars.
 Operations on contextfree languages and their closure properties. Pumping lemma for contextfree languages.
 Pushdown automata, (nondeterministic) topdown and bottomup syntax analysis. Deterministic pushdown languages.
 Turing machines.
 Recursive and recursively enumerable languages and their properties.
 Decidability, semidecidability, and undecidability of problems, reductions of problems.
 Computable functions. Other Turingcomplete computing mechanisms (automata with multiple pushdown 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, ...).
 Fundamental literature: 

 Kozen, D.C.: Automata and Computability, SpringerVerlag, New Yourk, Inc., 1997. ISBN 0387949070
 Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0201441241
 Martin, J.C.: Introduction to Languages and the Theory of Computation, McGrawHill, Inc., 3rd ed., 2002. ISBN 0072322004
 Brookshear, J.G.: Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0805301437
 Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, PrenticeHall, 1972. ISBN 0139145648
 Study literature: 

 Kozen, D.C.: Automata and Computability, SpringerVerlag, New Yourk, Inc, 1997. ISBN 0387949070
 Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0201441241
 Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997. ISBN 1850322430
 Controlled instruction: 

The participation of students is checked; a student can miss at most two lectures without a proper justification.  Exam prerequisites: 

A student can miss at most two lectures without a proper justification.  
