Základy teoretické informatiky I
doc. RNDr. Lucie Ciencialová, Ph.D.
Základy teoretické informatiky I

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

  1. Abeceda, formální jazyky, operace s formálními jazyky.
  2. Regulární jazyky, regulární výrazy.
  3. Konečné automaty.
  4. Uzávěrové vlastnosti regulárních jazyků.
  5. Chomského hierarchie jazyků.
  6. Regulární gramatiky a jejich vztah ke konečným automatům.
  7. Bezkontextové gramatiky, jejich varianty a vlastnosti.
  8. 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
Chapter contains:
2
PDF
1
Study text


Chapter contains:
1
ROPOT
1
Study text
Previous