Popis předmětu - AE4B01JAG

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
AE4B01JAG Languages, automata and grammars Rozsah výuky:2+2
Garanti:  Role:P,V Jazyk výuky:EN
Vyučující:  Zakončení:Z,ZK
Zodpovědná katedra:13101 Kreditů:6 Semestr:Z

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: AE4B01JAG

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

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

Literatura:

[1] J.E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation, Second Edition, Addison-Wesley, 2001

Požadavky:

Discrete Mathematics

Poznámka:

Rozsah výuky v kombinované formě studia: 14p+6s

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
BEKME_BO Před zařazením do oboru V 3
BEKME5 Komunikace a elektronika V 3
BEKME4 Síťové a informační technologie V 3
BEKME3 Aplikovaná elektronika V 3
BEKME2 Multimediální technika V 3
BEKME1 Komunikační technika V 3
BEEEM1 Aplikovaná elektrotechnika V 3
BEEEM_BO Před zařazením do oboru V 3
BEEEM2 Elektrotechnika a management V 3
BEOI1 Počítačové systémy P 3
BEOI3 Softwarové systémy P 3
BEOI_BO Před zařazením do oboru P 3
BEOI2 Informatika a počítačové vědy P 3
BEKYR_BO Před zařazením do oboru V 3
BEKYR3 Systémy a řízení V 3
BEKYR2 Senzory a přístrojová technika V 3
BEKYR1 Robotika V 3


Stránka vytvořena 11.12.2018 17:48:13, semestry: Z,L/2020-1, L/2017-8, L/2019-20, Z,L/2018-9, Z/2019-20, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.