Course details

Theoretical Computer Science 1

TI1 Acad. year 2004/2005 Winter semester 6 credits

Current academic year

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

Češka Milan, prof. RNDr., CSc.

Language of instruction

Czech

Completion

Credit+Examination

Time span

  • 39 hrs lectures
  • 12 hrs exercises
  • 2 hrs pc labs
  • 12 hrs projects

Department

Department of Intelligent Systems (UITS)

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.

Back to top