456-0906/01 – Theory of Languages and Automata (TJA)

Gurantor departmentDepartment of Computer ScienceCredits10
Subject guarantorprof. RNDr. Petr Jančar, CSc.Subject version guarantorprof. RNDr. Petr Jančar, CSc.
Study levelpostgraduateRequirementChoice-compulsory
YearSemesterwinter + summer
Study languageCzech
Year of introduction1997/1998Year of cancellation2009/2010
Intended for the facultiesFEIIntended for study typesDoctoral
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 3+0
Part-time Credit and Examination 3+0

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

Další požadavky na studenta

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

Full-time form (validity from: 1960/1961 Summer semester, validity until: 2008/2009 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2009/2010 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology K Czech Ostrava Choice-compulsory study plan
2008/2009 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2007/2008 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2006/2007 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2005/2006 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2004/2005 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2003/2004 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2002/2003 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2001/2002 (P2612) Electrical Engineering and Computer Science (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner