FPF:UIAI012 The Basic of Theoret. Comp. Sc - Course Information

UIAI012 The Basic of Theoretical Computer Science I

Extent and Intensity

2/2/0. 6 credit(s). Type of Completion: zk (examination).

Teacher(s)

prof. RNDr. Alice Kelemenová, CSc. (lecturer)
prof. RNDr. Alice Kelemenová, CSc. (seminar tutor)

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

• Applied Computer Science (programme FPF, B1802 AplI)

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

Language of instruction

Czech

Further Comments

The course can also be completed outside the examination period.

Teacher's information

Pass the oral exam from the scope of the course.

• Enrolment Statistics (Winter 2013, recent)
  
• Permalink: https://is.slu.cz/course/fpf/winter2013/UIAI012