Předmět Konečné automaty a formální jazyky (KVD / KAFJB)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KVD / KAFJB - Konečné automaty a formální jazyky, Fakulta pedagogická, Západočeská univerzita v Plzni (ZČU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
1. Deterministický konečný automat bez výstupu. Řetězec, délka řetězce, zřetězení slov.2. Klasifikační automat. Činnost automatu3. Způsoby reprezentace konečných automatů. Nedeterministický konečný automat4. Rozpoznávání řetězců nedeterministickým konečným automatem5. Konfigurace automatu. Převod nedeterministického konečného automatu na deterministický.6. Deterministický konečný automat s výstupem. Iniciální automat s výstupem7. Redukce konečného automatu. Ekvivalence automatů8. Formální jazyky. Jazyky rozpoznatelné konečnými automaty9. Gramatiky. Klasifikace gramatik. Nerodova věta10. Regulární jazyky a gramatiky. Regulární množiny. Regulární výrazy11. Převod regulárního výrazu na konečný automat. Převod nedeterministického konečného automatu na regulární výraz.12. Přechodové grafy. Kleenova věta. Vztah regulárních gramatik, regulárních jazyků a konečných automatů.13. Bezkontextové jazyky a gramatiky. Zásobníkový automat. Normální tvary bezkontextových gramatik.
Získané způsobilosti
Student získá teoretické základy pro další studium informatiky a elektroniky, atd. Bude schopen používat základní formální prostředky při řešení mnoha současných problémů, kdy implementace poznatků uváděné teorie povede k získání konkrétních výsledků. Jedná se například o návrh reálných automatů realizovaných jako sekvenční obvody.
Literatura
Demlová, Marie; Koubek, Václav. Algebraická teorie automatů. Praha : SNTL, 1990. ISBN 80-03-00348-2.Chytil, Michal. Automaty a gramatiky. Praha : SNTL, 1984. Molnár, Ludovít; Melichar, Bořivoj; Češka, Milan. Gramatiky a jazyky. Bratislava : Alfa, 1987. Manna, Zohar. Matematická teorie programů. Praha : SNTL, 1981. Kocur, Pavel. Úvod do teorie konečných automatů a formálních jazyků. Plzeň : Západočeská univerzita, 2001. ISBN 80-7082-813-7.
Požadavky
Zápočet: úspěšné splnění testů nebo vypracování a uznání samostatné práce.Zkouška: písemný test.
Garant
Ing. Pavel Kocur, CSc.
Vyučující
Mgr. Tomáš Přibáň, Ph.D.