Cíle výuky
V tomto předmětu se zabýváme především teoretickými základy metod používaných pro modelování struktur a postupů, tedy konečnými automaty, regulárními jazyky, regulárními výrazy a bezkontextovými gramatikami. Na teoretický základ navazují také příklady využití v praxi.
Tento předmět je sice o teorii, ale tato teorie má reálné využití v praxi. Struktury, které zde budeme probírat, používají především programátoři při vývoji programů zpracovávajících text s určitou vnitřní strukturou, například překladače programovacích jazyků, webové prohlížeče,...
Obsah
- Abeceda, formální jazyky, operace s formálními jazyky.
- Regulární jazyky, regulární výrazy.
- Konečné automaty.
- Uzávěrové vlastnosti regulárních jazyků.
- Chomského hierarchie jazyků.
- Regulární gramatiky a jejich vztah ke konečným automatům.
- Bezkontextové gramatiky, jejich varianty a vlastnosti.
- Zásobníkové automaty.
Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášek.
Doporučená literatura
Pokud se chcete v tématu dále vzdělávat, můžete použít například následující literaturu:
- MEDUNA, Alexander. Automata and languages: theory and applications. London: Springer, 2000, xv, 916 s. ISBN 18-523-3074-0.
- MEDUNA, Alexander a Petr ZEMEK. Regulated grammars and automata. New York: Springer, 2014. ISBN 978-1-4939-0368-9.
- LINZ, Peter. An introduction to formal languages and automata. Sixth edition. Burlington, MA: Jones, 2017. ISBN 978-128-4077-247.
- ČERNÁ, I., KŘETÍNSKÝ, M., KUČERA, A. Automaty a formální jazyky I, učební text FI MU. Brno, 2002.
- HOPCROFT, J.E., MOTWANI, R., ULLMAN, J.D. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1