FPF:UIAI019 The Basic of Theoret. Comp. Sc - Course Information
UIAI019 The Basic of Theoretical Computer Science II
Faculty of Philosophy and Science in OpavaWinter 2014
- Extent and Intensity
- 2/2/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- prof. RNDr. Alice Kelemenová, CSc. (lecturer)
RNDr. Šárka Vavrečková, Ph.D. (seminar tutor) - Guaranteed by
- prof. RNDr. Alice Kelemenová, CSc.
Institute of Computer Science – Faculty of Philosophy and Science in Opava - Prerequisites (in Czech)
- UIAI012 The Basic of Theoret. Comp. Sc || UIAI212 The Basis of Theoretical Compu || UIBUC56 Theory of languages and automa || UINK115 Theory of languages and automa || UIN1105 Theory of languages and automa
- 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
- Basic theorems of the classical formal language theory. We put emphasis to basic algorithms and proof techniques.
- Syllabus
- 1. Turing machine. Basic model.
2. Variants of the Turing machines.
3. Turing machines and grammars of type 0.
4. Generative power of the context-free grammars and acceptance of the pushdown automata.
5. Generative power of regular grammars and acceptance of the finite automata.
6. Chomsky hierarchy of formal languages. Typical examples.
7. Closure properties of language classes of Chomsky hierarchy with respect to union, catenation and iteration.
8. Closure properties of language classes of Chomsky hierarchy with respect to intersection.
9. Acceptation power of the pushdown automata with respect to the finite automata.
10. Acceptation power of the deterministic and nondeterministic pushdown automata
Exercises follow the content of lectures.
Literature
Harrison, M. A.: Introduction to Formal Language Theory. Addison-Wesley P. C. 1978.
Rozenberg, G., Salomaa, A. Eds.: Handbook of Formal Languages. Berlin: Springer, 1997.
Wood, D.: Theory of computation. New York: John Wiley & Sons, 1987.
- 1. Turing machine. Basic model.
- Language of instruction
- Czech
- Further Comments
- The course can also be completed outside the examination period.
- Teacher's information
- Credits from the exercises. Written exam - algorithms.
- Enrolment Statistics (Winter 2014, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2014/UIAI019