VSFS:N_AG Automaty a gramatiky - Informace o předmětu
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í.
- Statistika zápisu (zima 2016, nejnovější)
- Permalink: https://is.vsfs.cz/predmet/vsfs/zima2016/N_AG