N_AG Automaty a gramatiky

Vysoká škola finanční a správní
zima 2017
Rozsah
2/1/0. 12 hodin KS/semestr. 6 kr. Ukončení: zk.
Vyučující
prof. RNDr. Ondřej Čepek, Ph.D. (přednášející)
RNDr. Petr Tesař, Ph.D. (cvičící)
Garance
RNDr. Petr Tesař, Ph.D.
Katedra informatiky a matematiky (FES, KIM) – Katedry – Vysoká škola finanční a správní
Kontaktní osoba: Ivana Plačková
Rozvrh seminárních/paralelních skupin
N_AG/vAPH: Pá 1. 12. 14:00–15:30 S13, 15:45–17:15 S13, So 16. 12. 9:45–11:15 S13, 11:30–13:00 S13, Pá 5. 1. 17:30–19:00 S13, 19:15–20:45 S13, O. Čepek, 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
Cílem studijního předmětu je seznámit studenty s problematikou konečných automatů a formálních jazyků. Zvýšená pozornost je věnována bezkontextovým gramatikám neboť prakticky všechny programovací počítačové jazyky jsou definovány pomocí bezkontextových gramatik. Při překladu zdrojových textů programů se využívají vlastnosti bezkontextových gramatik v návaznosti na zásobníkové automaty.
Výstupy z učení
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, Greibachova 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ů.
Informace učitele
Přednášky ve formátu pdf budou zasílány studentům vždy po provedené přednášce
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 2016, zima 2018, zima 2019, zima 2020, zima 2021, zima 2022, zima 2023, zima 2024.