ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

# Languages, automata and grammars

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
AE4B01JAG Z,ZK 6 2+2
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.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/AE4B01JAG

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ů:
Platnost dat k 29. 1. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet12818904.html