Languages, automata and grammars
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
AE4B01JAG | Z,ZK | 6 | 2+2s | česky |
- Podmínkou zápisu předmětu je, že student získal v předchozích semestrech zápočet z následujících předmětů:
- Discrete mathematics (AE4B01DMA)
- Přednášející:
- Cvičící:
- Předmět zajišťuje:
- katedra matematiky
- Anotace:
-
The course covers basics of the theory of finite automata and grammars: deterministic and nondeterministic finite automata, characterization of the class of languages accepting by a finite automaton and description of such a language by a regular expression. Grammars and languages generated by a grammar, context-free grammars will be emphasized. The relation will be shown between context-free grammars and push down automata. Next topic is a Turing machine and the existence of non-decidable problems.
- Požadavky:
-
Discrete Mathematics
- Osnova přednášek:
-
1.Alphabet, strings over an alphabet, concatenation of words, language.
2.Deterministic finite automaton, state diagram.
3.Language accepted by a finite automaton, Nerode?s Theorem.
4.Nondeterministic finite automata.
5.Equivalence of deterministic and nondeterministic finite automata.
6.Regular expressions and regular languages, Kleen?s Theorem.
7.Properties of regular languages.
8.Grammars, regular grammars, context-free grammars.
9.Push down automata and their relation to context-free languages.
10.Properties of context-free languages, Pumping Lemma for context-free languages.
11.Algorithms for some problems concerning context-free languages.
12.Turing machines.
13.Non-decidable problems.
- Osnova cvičení:
-
1.Alphabet, strings over an alphabet, concatenation of words, language.
2.Deterministic finite automaton, state diagram.
3.Language accepted by a finite automaton, Nerode?s Theorem.
4.Nondeterministic finite automata.
5.Equivalence of deterministic and nondeterministic finite automata.
6.Regular expressions and regular languages, Kleen?s Theorem.
7.Properties of regular languages.
8.Grammars, regular grammars, context-free grammars.
9.Push down automata and their relation to context-free languages.
10.Properties of context-free languages, Pumping Lemma for context-free languages.
11.Algorithms for some problems concerning context-free languages.
12.Turing machines.
13.Non-decidable problems.
- Cíle studia:
- Studijní materiály:
-
[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001
- Poznámka:
-
Rozsah výuky v kombinované formě studia: 14p+6s
- Další informace:
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů:
-
- Open Informatics - Computer Systems (povinný předmět programu)
- Open Informatics - Computer and Information Science (povinný předmět programu)
- Open Informatics - Software Systems (povinný předmět programu)
- Open Informatics (povinný předmět programu)