Course details
Theoretical Computer Science 1
TI1 Acad. year 2004/2005 Winter semester 6 credits
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.
Guarantor
Language of instruction
Completion
Time span
- 39 hrs lectures
- 12 hrs exercises
- 2 hrs pc labs
- 12 hrs projects
Department
Subject specific learning outcomes and competences
Theoretical knowledge for application in problems of compiler construction, system modelling, formal specification, verification and artificial intelligence.
Learning objectives
Adoption of fundamental concepts and results of formal language theory used in compiler construction, computability, and system modelling.
Prerequisite knowledge and skills
There are no prerequisites
Syllabus of lectures
- Introduction to formal languages
- Operations on formal languages and algebraic properties of formal languages
- Grammars, derivation relations, the language specified by a grammar
- Chomsky classification and hierarchy of formal languages
- Finite automata
- Regular expressions
- Reduced form of finite automaton
- Properties of regular languages
- Context free grammars and languages, derivation trees
- Transformations on context free grammars
- Pushdown automata equivalence problem, deterministic pushdown automata and context free languages
- Properties of context free and deterministic context free languages.
- Petri nets
Syllabus of numerical exercises
- Operations on formal languages, grammars, derivation relations, the language specified by a grammar, Chomsky classification and hierarchy of formal languages
- Finite automata, regular expressions, equivalent representation of regular languages.
- Reduced form of finite automaton, properties of regular languages
- Context free grammars and languages, derivation trees
- Transformations on context free grammars
- Pushdown automata equivalence problem, properties of context free languages.
Syllabus of computer exercises
- Petri net tool PESIM.
Progress assessment
Duty credit consists of mid-term exam passing and of obtaining at least 25 points for activities during semester (a mid-term exam, homeworks).
Controlled instruction
Written mid-term exam, check points for projects elaboration.