Základními tématy předmětu jsou abstraktní stroje, formální gramatiky a jazyky, pojem vyčíslitelnosti a složitosti automatů, jazyků a výpočtů. Bude diskutováno chování individuálních objektů i fenoménů a důsledky spolupráce kolektivního chování objektů. Studenti se seznámí s Turingovým strojem, zásobníkovým automatem a konečným automatem, se vztahem strojů a formálních gramatik. Předmětem studia bude také omezení strojového přístupu a generativního přístupu k řešení úloh a související pojem (ne)rozhodnutelnosti. 

Osnova

1. Abeceda, slovo,  jazyk
2. Konečná reprezentace jazyků
3. Gramatiky
4. Konečné automaty a regulární jazyky
5. Zásobníkové automaty
6. Bezkontextové gramatiky a jazyky
7. Úvod do teorie vyčíslitelnosti

Požadavky na studenta

Zkouška probíhá formou písemného testu, který obsahuje jak otázky na teorii tak příklady k vyřešení.

Literatura

Povinná:

1. CIENCIALOVÁ, L., Teoretické základy informatiky. Opava 2014. ISBN: 978 – 80 –7510 – 130 – 3 

Doporučená:

1. DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990. 
2. CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. 
3. GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. 
4. MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: Alfa, 1987. 
5. HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987.