460-6003/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 levelpostgraduate
Study languageCzech
Year of introduction2010/2011Year of cancellation
Intended for the facultiesFEIIntended for study typesDoctoral
Instruction secured by
LoginNameTuitorTeacher giving lectures
JAN59 prof. RNDr. Petr Jančar, CSc.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Examination 28+0
Combined Examination 28+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; an emphasis is put on the rigorous approach and deeper understanding. The course is then 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:

M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006

Recommended literature:

D. Kozen: Automata and Computability, Springer 1997 D. Kozen: Theory of Computation; Springer 2006 J.E.Hopcroft, R. Motwani, J.D.Ullman: Introduction to Automata Theory, Languages and Computation. Addison Wesley, 2001 H. Comon et al.: Tree Automata Techniques and Applications; http://tata.gforge.inria.fr/ (2007) Handbook of formal languages, Vol 1,2,3 (ed. G.Rozenberg) (Springer 1997)

Way of continuous check of knowledge in the course of semester

The student writes a concise, cogent and understandable article about a selected advanced topic, which he/she presents during the course.

E-learning

Další požadavky na studenta

There are not defined other requirements for student.

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

The notion of formal language. Operations with formal languages. Regular languages. Specification of languages. Rewriting systems and grammars. Chomsky's classification of grammars. Finite automata: dterministic, nondeterministic. Languages recognized by finite automata. Kleene's Theorem. Automata morphisms, minimization of finite automata. Finite automata and regular grammars. Context-free grammars. Pushdown automata. Languages generated by context-free grammars and recognized by pushdown automata. Context-sensitive languages generated by context grammars and recognized by linear bounded automata. Turing machines. Languages accepted and recognized by Turing machines (recursively enumerable and recursive languages). Post's Theorem. Algorithmic solvability. Church-Turing thesis. Further topics in the area of finite automata (2-way automata, automata with weights, ...) Further topics in the area of context-free languages (deterministic context-free languages, ...) Tree languages Relation of languages, automata, and logical theories Further selected topics

Conditions for subject completion

Full-time form (validity from: 2013/2014 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Examination Examination  
Mandatory attendence parzicipation:

Show history
Combined form (validity from: 2013/2014 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Examination Examination  
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (P0541D170005) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory type B study plan
2019/2020 (P0541D170005) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory type B study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2018/2019 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2017/2018 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2016/2017 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2015/2016 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2014/2015 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K English Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2013/2014 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2012/2013 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2011/2012 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2010/2011 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2010/2011 (P2646) Information Technology (1801V002) Computer Science and Applied Mathematics K Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics P Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1801V001) Informatics K Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics P Czech Ostrava Choice-compulsory study plan
2010/2011 (P1807) Computer Science, Communication Technology and Applied Mathematics (1103V036) Computational and Applied Mathematics K Czech Ostrava Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner