Title:

Theoretical Computer Science 1

Code:TI1
Ac.Year:ukončen 2004/2005
Term:Winter
Study plans:
ProgramBranchYearDuty
EI-BC-3VTB2nd Stage/2nd YearElective
EI-MSC-3VTN1stCompulsory
EI-MSC-5VTI2nd Stage/1st YearCompulsory
Language:Czech
Public info:http://www.fit.vutbr.cz/study/courses/TI1/public/
Credits:6
Completion:accreditation+exam (written)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:39120212
 ExaminationTestsExercisesLaboratoriesOther
Points:60200020
Guarantee:Češka Milan, prof. RNDr., CSc., DITS
Lecturer:Češka Milan, prof. RNDr., CSc., DITS
Instructor:Marek Vladimír, Ing., DITS
Rogalewicz Adam, Mgr., Ph.D., DITS
Vojnar Tomáš, prof. Ing., Ph.D., DITS
Faculty:Faculty of Information Technology BUT
Department:Department of Intelligent Systems FIT BUT
Prerequisites: 
Algebra and Graphs (AGR), DMAT
Algorithms and Programming (APR), DIFS
Follow-ups:
Computability and Complexity (VSL), DITS
Modelling and Simulation (MSI), DITS
Principles of Compiler Design (ZAP), DIFS
Theoretical Computer Science 2 (TI2), DITS
 
Learning objectives:
Adoption of fundamental concepts and results of formal language theory used in compiler construction, computability, and system modelling.
Description:
Applications of formal language theory, operations over formal languages, the problem of language specification, grammars, Chomsky hierarchy of formal languages, finite state automata, regular sets and expressions, Kleen's theorem, minimal finite automata, properties of regular languages, context-free grammars, syntactical analysis, transformations on context-free grammars, push-down automata and context-free languages, properties of context-free languages, Petri nets.
Learning outcomes and competences:
Theoretical knowledge for application in problems of compiler construction, system modelling, formal specification, verification and artificial intelligence.
Syllabus of lectures:
  1. Introduction to formal languages
  2. Operations on formal languages and algebraic properties of formal languages
  3. Grammars, derivation relations, the language specified by a grammar
  4. Chomsky classification and hierarchy of formal languages
  5. Finite automata
  6. Regular expressions
  7. Reduced form of finite automaton
  8. Properties of regular languages
  9. Context free grammars and languages, derivation trees
  10. Transformations on context free grammars
  11. Pushdown automata equivalence problem, deterministic pushdown automata and context free languages
  12. Properties of context free and deterministic context free languages.
  13. Petri nets
Syllabus of numerical exercises:
  1. Operations on formal languages, grammars, derivation relations, the language specified by a grammar, Chomsky classification and hierarchy of formal languages
  2. Finite automata, regular expressions, equivalent representation of regular languages.
  3. Reduced form of finite automaton, properties of regular languages
  4. Context free grammars and languages, derivation trees
  5. Transformations on context free grammars
  6. Pushdown automata equivalence problem, properties of context free languages.
Syllabus of computer exercises:
  1. Petri net tool PESIM.
Syllabus - others, projects and individual work of students:
Six homework assignments.
Fundamental literature:
  1. Aho A.V.,Ullmann J.D.: The Theory of Parsing, Translation and Compiling, Prentice-Hall, 1972
  2. Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 1991.
  3. Češka M.: Petriho sítě, Akad.nakl. CERM, Brno 1994
Study literature:
  1. Melichar B. a kol.: Gramatiky a jazyky SNTL, 1987
  2. Češka M.,Rábová Z. Gramatiky a jazyky Nakl. VUT Brno, 1992
  3. Češka M.a kol.: Vyčíslitelnost a složitost, Nakl. VUT Brno, 1993
  4. Češka M.: Petriho sítě, Akad.nakl. CERM, 1994
Controlled instruction:
Written mid-term exam, check points for projects elaboration.
Progress assessment:
Mid-term exam evaluation and evaluation of projects dokumentation.
Exam prerequisites:
Duty credit consists of mid-term exam passing and of obtaining at least 25 points for activities during semester (a mid-term exam, homeworks).