UIAI212 The Basis of Theoretical Computer Science I

Faculty of Philosophy and Science in Opava
Summer 2016
Extent and Intensity
0/0. 7 credit(s). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Alice Kelemenová, CSc. (lecturer)
RNDr. Šárka Vavrečková, Ph.D. (lecturer)
Guaranteed by
prof. RNDr. Alice Kelemenová, CSc.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
The course introduces into the issue of the theoretical computer science. Students get familiar with terms like terminal and non-terminal symbols, alphabet, words, and language. Students get familiar also with formal grammars, Chomski hierarchy of the grammars, especially regular and context-free grammars and their normal forms, finite and push-down automata, (non)equivalence of deterministic and non-deterministic.
Syllabus
  • 1. Terminal and nonterminal symbols, words, sentences, sentential forms, languages, family of languages
    2. Operations over alphabets, words, languages
    3. Formal grammars
    4. Chomski hierarchy of the grammars
    5. Regular grammars, family of the regular languages, regular expressions
    6. Finite automata, equivalence of deterministic and nondeterministic FA, minimization of FA
    7. Context-free grammars, normal forms and transformations of CFG
    8. Push-down automaton, non-equivalence of deterministic and nondeterministic PDA
    9. Pumping lemma for CFG
Teaching methods
Interactive lecture
Lecture with a video analysis
Assessment methods
Exam
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
Information on the extent and intensity of the course: Přednáška 6 HOD/SEM.
Teacher's information
Pass the oral exam from the scope of the course.
The course is also listed under the following terms Winter 2012, Winter 2013, Summer 2015, Summer 2017, Summer 2018, Summer 2019, Summer 2020, Summer 2021, Summer 2022, Summer 2023.
  • Enrolment Statistics (Summer 2016, recent)
  • Permalink: https://is.slu.cz/course/fpf/summer2016/UIAI212