N_AG Automaty a gramatiky

Vysoká škola finanční a správní
zima 2016
Rozsah
2/1/0. 12 hodin KS/semestr. 6 kr. Ukončení: zk.
Vyučující
RNDr. Petr Tesař, Ph.D. (cvičící)
Garance
prof. Ing. Petr Berka, CSc.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Ing. Barbora Ptáčková
Rozvrh seminárních/paralelních skupin
N_AG/vAPH: Pá 4. 11. 17:30–19:00 S13, Pá 18. 11. 17:30–19:00 S13, Pá 2. 12. 15:45–17:15 S13, 17:30–19:00 S13, Pá 16. 12. 14:00–15:30 S14, 15:45–17:15 S14, P. Tesař
Předpoklady
Nejsou vyžadovány žádné předpoklady.
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
Na konci tohoto kurzu bude student schopen používat automaty (zejména konečné a zásobníkové) a gramatiky jako formální prostředky popisu jazyka či chování softwaru, případně k modelování chování softwar, resp. jeho částí. Znalosti a dovednosti nabyté v tomto předmětu mu v mnoha případech umožní rozpoznat obtížnost úlohy a vyhledat možná řešení.
Osnova
  • 1) Úvod. Pojmy z teorie množin. Definice konečného automatu. Reprezentace konečného automatu
  • 2) Jazyky rozpoznatelné konečnými automaty. Nerodova věta. Kritéria pro návrh konečného automatu
  • 3) Definice nedeterministického konečného automatu. Vztah jazyků rozpoznatelných nedeterministickým konečným automatem a rozpoznatelnosti deterministickým konečným automatem. Definice zobecněného nedeterministického konečného automatu. Vztah jazyků rozpoznatelných zobecněným nedeterministickým konečným automatem a rozpoznatelnosti konečným automatem
  • 4) Množinové operace s jazyky, sjednocení, průnik, doplněk, rozdíl, součin (zřetězení), levý/pravý kvocient jazyka podle dalšího jazyka, levá/pravá derivace podle slova. Substituce z jazyka, nevypouštějící substituce z jazyka, homomorfismus, nevypouštějící homomorfismus. Uzavřenost třídy jazyků rozpoznatelných konečnými automaty vůči některým množinovým operacím. Definice třídy regulárních jazyků nad konečnou abecedou. Vztah regulárních jazyků a konečných automatů - Kleeneova věta
  • 5) Definice přepisovacího systému. Pojem posloupnosti vzniklé odvozením (nebo derivací) délky n slova z ze slova u. Definice generativní gramatiky, nonterminál, terminál, přepisovací pravidla, jazyk generovaný generativní gramatikou. Definice analytické gramatiky a její vztah ke generativní gramatice. Chomského hierarchie gramatik (a jimi generovaných jazyků)
  • 6) Definice nevypouštějící bezkontextové gramatiky a vztah s bezkontextovou gramatikou. Vztah mezi jazyky rozpoznatelnými konečným automatem a jazyky typu 3 dle Chomského. Definice levé lineární gramatiky a vztah ke gramatikám typu 3. Definice lineární gramatiky. Vztah mezi třídou regulárních jazyků a třídou lineárních jazyků
  • 7) Redukované gramatiky. Kanonická derivace, derivační stromy, jednoznačné gramatiky. Analýza shora
  • 8) Zásobníkové automaty a bezkontextové gramatiky. Analýza zdola. Chomského normální forma
  • 9) Definice jednoduché LL(1) gramatiky. Definice LL(1) analyzátoru. Vztah LL(1) gramatiky a LL(1) analyzátoru
  • 10) Definice LR(0) gramatiky. Vztah LR(0) gramatiky a deterministického zásobníkového automatu
  • 11) Definice Turingova stroje (dále jen TS). Konfigurace TS. Počáteční konfigurace TS, bezprostředně následující konfigurace TS a koncová konfigurace TS. Jazyk rozpoznávaný TS. Vztah mezi jazykem rozpoznatelným TS a jazyky Typu 0
  • 12) Definice rekurzivního jazyka. Definice rekurzivně spočetného jazyk. Vztah mezi rekurzivními jazyky a rekurzivně spočetnými jazyky – Postova věta
Literatura
    povinná literatura
  • M. Chytil: Automaty a gramatiky, Praha, SNTL, 1984
Výukové metody
Teoretická příprava, příklady.
Metody hodnocení
Předmět je zakončen ústní zkouškou, která sestává z jedné otázky. Okruh otázek pokrývá celou přednesenou oblast. Ke zkoušce je připuštěn pouze student, který předtím získá zápočet z předmětu N_AG. Pro získání zápočtu je nutné v písemném testu sestávajícím z 3 příkladů získat minimálně 50% bodů.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 2014, zima 2015, zima 2017, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023, zima 2024.