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

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 BEKME1 Komunikační technika V 3 BEKME5 Komunikace a elektronika V 3 BEKME_BO Před zařazením do oboru V 3 BEKME4 Síťové a informační technologie V 3 BEKME3 Aplikovaná elektronika V 3 BEKME2 Multimediální 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 BEOI_BO Před zařazením do oboru P 3 BEOI3 Softwarové systémy P 3 BEOI2 Informatika a počítačové vědy P 3 BEKYR1 Robotika V 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

 Stránka vytvořena 26.6.2019 17:51:10, semestry: Z,L/2020-1, L/2018-9, Z,L/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.