456-0906/01 – Theory of Languages and Automata (TJA)
Gurantor department | Department of Computer Science | Credits | 10 |
Subject guarantor | prof. RNDr. Petr Jančar, CSc. | Subject version guarantor | prof. RNDr. Petr Jančar, CSc. |
Study level | postgraduate | Requirement | Choice-compulsory |
Year | | Semester | winter + summer |
| | Study language | Czech |
Year of introduction | 1997/1998 | Year of cancellation | 2009/2010 |
Intended for the faculties | FEI | Intended for study types | Doctoral |
Subject aims expressed by acquired skills and competences
On successful completion of the course, the student
- understands the notions from automata and language theory
- is able to choose an appropriate formal language for description of
practical problems and understands possibilities and limitations of
various automata classes in connection with practical problems
solving
- is able by self-study to master and present an advanced topic (e.g.
from the area of program verification)
Teaching methods
Lectures
Individual consultations
Project work
Summary
The course first recapitulates basic knowledge concerning finite automata, context-free languages and Turing machines from the master studies, and then it is devoted to some advanced parts in these and further areas (including, e.g., relation of languages and automata with logic, tree languages etc.).
Compulsory literature:
J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory, Languages and
Computation. Addison Wesley, 1978
Recommended literature:
Handbook of formal languages, Vol 1,2,3 (ed. G.Rozenberg) (Springer 1997)
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Přednášky:
Pojem formálního jazyka. Operace s jazyky. Regulární jazyky.
Specifikace
jazyků. Přepisovací systémy a gramatiky. Chomského klasifikace gramatik.
Konečné automaty: deterministické, nedeterministické, zobecněné
nedeterministické. Jazyky rozpoznávané konečnými automaty. Kleeneho věta.
Automatové morfismy a minimalizace konečných automatů. Konečné automaty a
regulární gramatiky.
Bezkontextové gramatiky. Zásobníkové automaty. Jazyky
generované bezkontextovými gramatikami a rozhodované zásobníkovými automaty.
Kontextové jazyky generované
kontextovými gramatikami a rozpoznávané lineárně omezenými automaty. Turingovy
stroje. Jazyky rozpoznávané a rozhodované Turingovými stroji /rekurzivně
spočetné a rekurzivní jazyky/. Postova věta. Algoritmická řešitelnost.
Turingova /Churchova/ téze.
Další partie teorie konečných automatů (dvoucestné automaty, automaty s váhami, ...)
Další partie teorie bezkontextových jazyků (deterministické bezkontextové jazyky, ...)
Stromové jazyky
Vztah jazyků, automatů a logických teorií
Další vybrané partie
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.