NTIN071 Automaty a gramatiky: cvičení (Jaro 2024)

Zde najdete informace k mým českým cvičením (Pondělí 9:00 v S7 a 10:40 v S6).

Konzultační hodiny během výuky (v S303):

pondělí 12:20
středa 14:00 (22. května zrušeny z důvodu předtermínu)
čtvrtek 15:40

nebo individuálně po předchozí domluvě emailem. (Pokud plánujete přijít později, prosím napište.)

Konzultace během zkouškového období rozvrhujeme dle potřeby - napište mi v dostatečném předstihu své časové možnosti.

Zápočet

Podmínky pro získání zápočtu jsou popsány zde.
Domácí úkol: termín odevzdání 6. 5. na začátku cvičení, zadání: domaci-ukol.pdf
Zápočtový test: termín 13. 5., seznam-pozadavku.pdf, vzorovy-test.pdf

Program cvičení

1. cvičení (19. 2.)

Program: Deterministický konečný automat, rozpoznávaný jazyk
Materiály: cviceni1.pdf

2. cvičení (26. 2.)

Program: Regulární jazyky, Pumping lemma
Materiály: cviceni2.pdf

3. cvičení (4. 3.)

Program: Myhill-Nerodeova věta, ekvivalentní a minimální reprezentace, testování vlastností
Materiály: cviceni3.pdf

4. cvičení (11. 3.)

Program: Nedeterminismus, uzavřenost na operace
Materiály: cviceni4.pdf

5. cvičení (18. 3.)

Program: Uzavřenost na operace
Materiály: zbylé příklady z cviceni4.pdf

6. cvičení (25. 3.)

Program: Regulární výrazy
Materiály: cviceni6.pdf

7. cvičení (8. 4.)

Program: Formální gramatiky, regulární a bezkontextové gramatiky, bonus: dvousměrné automaty
Materiály: cviceni7.pdf

8. cvičení (15. 4.)

Program: Chomského normální forma, Algoritmus CYK
Materiály: cviceni8.pdf

9. cvičení (22. 4.)

Program: Pumping lemma pro bezkontextové jazyky
Materiály: cviceni9.pdf

10. cvičení (29. 4.)

Program: Zásobníkové automaty
Materiály: cviceni10.pdf

11. cvičení (6. 5.)

Program: Termín odevzdání domácího úkolu! Turingovy stroje
Materiály: cviceni11.pdf

12. cvičení (13. 5.)

Program: Zápočtový test!

13. cvičení (20. 5.)

Program: Více o Turingových strojích, úvod do výpočetní složitosti
Materiály: Pokračujeme v cviceni11.pdf

Užitečné odkazy

Často kladené dotazy

Co mám dělat, pokud mám otázku ke cvičení? – Podívejte se sem do ČKD. Pokud nenajdete odpověď, napište mi email; do předmětu zprávy, prosím, napište “ntin071” a “cvičení”.
Co mám dělat, pokud chci konzultaci? – Domluvte se se mnou po cvičení, přijďte na rozvržené konzultační hodiny, nebo si domluvme termín konzultace emailem.