Fakulta elektrotechnická

České vysoké učení technické v Praze

ČVUT v Praze

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
BEKME3 Aplikovaná elektronika V 3
BEKME5 Komunikace a elektronika V 3
BEKME2 Multimediální technika V 3
BEKME1 Komunikační technika V 3
BEKME_BO Před zařazením do oboru V 3
BEKME4 Síťové a informační technologie V 3
BEEEM_BO Před zařazením do oboru V 3
BEEEM2 Elektrotechnika a management V 3
BEEEM1 Aplikovaná elektrotechnika V 3
BEOI2 Informatika a počítačové vědy P 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
BEKYR_BO Před zařazením do oboru V 3
BEKYR1 Robotika V 3
BEKYR2 Senzory a přístrojová technika V 3
BEKYR3 Systémy a řízení V 3


Stránka vytvořena 12.12.2017 12:48:10, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, 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.