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 (v S303):

• pondělí 12:20
• středa 14:00
• čtvrtek 15:40

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

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: cviceni13.pdf

Užitečné odkazy

• Turing Machine Simulator
• Finite State Machine designer

Č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.