Fakulta elektrotechnická

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

ČVUT v Praze

Popis předmětu - XP01TJA

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
XP01TJA Teorie jazyků a automatů Rozsah výuky:2+1
Garanti:Demlová M. Role:S Jazyk výuky:CS
Vyučující:Demlová M. Zakončení:ZK
Zodpovědná katedra:13101 Kreditů:4 Semestr:L

Anotace:

Konečné automaty. Nerodova věta a její aplikace, redukce automatu. Nedeterministické automaty též s e-přechody. Regulární výrazy a Kleeneova věta. Gramatiky a jejich klasifikace. Bezkontextové gramatiky, jejich redukce. Zásobníkové automaty. Vztah mezi zásob. automaty a bezkontextovými gramatikami. Chomského normální tvar, lemma ovkládání. Algoritmus CYK pro bezkontextové gramatiky. Turingovy stroje jako akceptory a jako počítače funkcí. Nerozhodnutelnost problému zastavení Turingova stroje. Další algoritmicky neřešitelné úlohy.

Osnovy přednášek:

Osnovy cvičení:

Literatura:

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.

Požadavky:

Poznámka:

Předmět je nabízen jednou za dva roky.

Webová stránka:

http://math.feld.cvut.cz/demlova/teaching/tja.htm

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

Plán Obor Role Dop. semestr
DOKK Před zařazením do oboru S
DOKP Před zařazením do oboru S


Stránka vytvořena 20.4.2018 17:47:30, semestry: L/2018-9, 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.