Automaty a gramatiky - NTIX071

• Anglický název: Automata and Grammars
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 6
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NTIN071
• Další informace: https://dl1.cuni.cz/course/view.php?id=5119
• Garant: Mgr. Marta Vomlelová, Ph.D.
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Teoretická informatika
• Prerekvizity : {NXXX015, NXXX018, NXXX022, NXXX023, NXXX024, NXXX025, NXXX030, NXXX031, NXXX033, NXXX065}
• Neslučitelnost : NTIN071
• Záměnnost : NTIN071
• Je neslučitelnost pro: NTIN071
• Je záměnnost pro: NTIN071

Anotace

čeština

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

angličtina

Introductory lectures on Automata Theory and Formal Grammars. The emphasis is put on basic terminology and fundamental results. We study and highlight connections between the following formal models: finite-state and push-down automata (both deterministic and non-deterministic), Turing machines (including the halting problem), regular, context-free, and context-sensitive grammars.

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

Cíl předmětu

čeština

Naučit základy teorie automatů a gramatik, zejména o regulárních a bezkontextových jazycích a základních třídách složitosti.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)

angličtina

The course gives an introduction to automata theory and formal languages. The students will learn the following formal models and their basic properties:

finite-state and push-down automata (both deterministic and non-deterministic), Turing machines (including the halting problem), regular, context-free, and context-sensitive grammars and languages.

Poslední úprava: Otto Friedrich, Dr. (08.02.2018)

Podmínky zakončení předmětu

čeština

Formou kontroly studia předmětu je zápočet a zkouška. Získání zápočtu je nutnou podmínkou pro absolvování zkoušky.

Zápočet udělují vyučující na jednotlivých cvičeních především na základě bodového hodnocení závěrečného testu, část bodů je možné udělit za aktivitu v podobě případných domácích úloh, aktivity na cvičeních apod. Opakovat lze pouze závěrečný test, nikoli aktivitu v průběhu semestru.

V případě epidemie možné, že se část zkoušek či zápočtů bude konat distanční formou. Závisí to na vývoji aktuální situace a o jakékoli změně budete včas informováni.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)

angličtina

The form of study verification is a credit and an exam. Obtaining credit first is a necessary condition for taking an exam, with the exception of early exam terms. The credit is granted by teachers leading the tutorials based on point evaluation of tests during the semester, possible homeworks, activity etc. The nature of study verification for the credit excludes the possibility of its repetition.

The exam consists of written and oral parts. The written part precedes the oral part. If the written part is evaluated as unsatisfactory, the exam ends as unsatisfactory without taking the oral part. If the oral part is evaluated as unsatisfactory, the student has to repeat both written and oral parts on the next exam term. Final exam grade is based on evaluation of both written and oral parts.

Examples of the written part from previous years are available on the course webpage.

Demands at oral part correspond to the syllabus of the course in the extend that has been presented on lectures.

We may expect that substantial part of credits and exams is performed remotely. Written part of the exam can be replaced by moodle test, oral part performed remotely. The details depend on the actual situation and you will be noticed on any change.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (27.04.2020)

Literatura

čeština

• J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
• M. Sipser: Introduction to the Theory of Computation, Cengage Learning, 2013
• M. Chytil: Automaty a gramatiky, SNTL Praha, 1984
• V. Koubek: Automaty a gramatiky, elektronický text (http://ktiml.mff.cuni.cz/ktiml/teaching/files/materials/Automstr_ps.zip), 1996
• M. Chytil: Teorie automatů a formálních jazyků, skripta MFF UK, 1978
• M. Chytil: Sbírka řešených příkladů z teorie automatů a formálních jazyků, skripta MFF UK, 1987
• M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL Praha, 1990
• Videozáznamy přednášek

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)

angličtina

J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

M. Sipser: Introduction to the Theory of Computation, Cengage Learning, 2013

P.J. Denning, J.E. Dennis, J.E. Qualitz: Machines, Languages, and Computation, Prentice-Hall, 1978

M. Harrison: Introduction to Formal Language Theory, Addison-Wesley, 1978

H.R. Lewis, Ch.H. Papadimitriou: Elements of the Theory of Computation, Prentice-Hall, 1981

G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Language Theory, Vol.1: Word, Language, Grammar, Springer, 1997

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (25.01.2024)

Metody výuky

čeština

přednáška a cvičení

Poslední úprava: BARTAK/MFF.CUNI.CZ (31.03.2008)

angličtina

Lectures and exercises

Poslední úprava: Otto Friedrich, Dr. (08.02.2018)

Požadavky ke zkoušce

čeština

Zápočet je nutnou podmínkou účasti na zkoušce.

Zkouška sestává z písemné přípravy a ústní části. Písemná část předchází části ústní, její nesplnění znamená, že celá zkouška je hodnocena známkou nevyhověl(a) a ústní částí se již nepokračuje.

Nesložení ústní části znamená, že při příštím termínu je nutno opakovat obě části zkoušky, písemnou i ústní. Známka ze zkoušky se stanoví na základě bodového hodnocení písemné i ústní části.

Písemná část bude sestávat ze tří otázek, které korespondují obsahem přednášky, ověřují schopnosti získané na cvičení a znalost definic, vět a algoritmů z přednášky.

Požadavky ústní části odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce. Zpravidla se jedná o detailnější rozbor zadaného problému, např. zdůvodnění zařazení daného jazyka do Chomského hierarchie či důkaz klíčových vět.

V případě epidemie možné, že se značná část zkoušek či zápočtů může konat distanční formou. Za ekvivalent písemného testu se považuje zkouškový test moodle, ústní zkoušení může probíhat distanční formou.

Závisí to na vývoji aktuální situace a o jakékoli změně budete včas informováni.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)

angličtina

Credits from exercises are a necessary condition to attend the final exam.

The final exam consists from a written part and a possible additional oral part. The exam will test the acquired understanding of the definitions, theorems, and algorithms presented during the course.

We may expect that substantial part of credits and exams is performed remotely. Written part of the exam can be replaced by moodle test, oral part performed remotely. The details depend on the actual situation and you will be noticed on any change.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (27.04.2020)

Sylabus

čeština

Konečné automaty a regulární jazyky, Nerodova věta, ekvivalence a redukce automatů, nedeterminismus.

Uzávěrové vlastnosti, regulární výrazy, Kleeneova věta, pumping (iterační) lemma pro regulární jazyky.

Gramatiky, Chomského hierarchie, regulární, bezkontextové a obecné gramatiky

Bezkontextové gramatiky, derivace, normální tvary, pumping (iterační) lemma pro bezkontextové jazyky, zásobníkové automaty.

Rekurzivně spočetné jazyky, Turingovy stroje, algoritmicky nerozhodnutelné problémy, univerzální jazyk, diagonální jazyk.

Polynomiální složitost, NP-úplnost, Cook-Levinova věta.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (07.02.2024)

angličtina

Word, language, operations on languages

Formal grammar, regular grammar, finite-state automaton, Nerode's Theorem, minimal automaton, non-determinism

Closure properties of the class of regular languages, regular expressions, Kleene's Theorem, Pumping Lemma for regular languages

Finite-state transducer, decision problems for regular languages

Context-free grammar, Chomsky normal form, Greibach normal form, closure properties of the class of context-free languages, Pumping Lemma for context-free languages

Pushdown automaton, CYK-algorithm, deterministic pushdown automaton, decision problems for context-free languages

Context-sensitive grammar, context-sensitive language, closure properties and decision problems, linear-bounded automaton

Turing machines, halting problem, reduction, undecidable problems, recursively enumerable language, Chomsky hierarchy, the universal language, the diagonal language.

Poslední úprava: Vomlelová Marta, Mgr., Ph.D. (13.05.2019)