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 | English | ||

Year of introduction | 2015/2016 | Year of cancellation | |

Intended for the faculties | FEI | Intended for study types | Doctoral |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

JAN59 | prof. RNDr. Petr Jančar, CSc. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Examination | 28+0 |

Combined | Examination | 28+0 |

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)

Lectures

Individual consultations

Project work

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.).

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

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)

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

There are not defined other requirements for student.

Subject has no prerequisities.

Subject has no co-requisities.

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

Task name | Type of task | Max. number of points
(act. for subtasks) | Min. number of points |
---|---|---|---|

Examination | Examination |

Show history

Academic year | Programme | Field of study | Spec. | Form | Study language | Tut. centre | Year | W | S | Type of duty | |
---|---|---|---|---|---|---|---|---|---|---|---|

2019/2020 | (P0541D170006) Computational and Applied Mathematics | P | English | Ostrava | Choice-compulsory type B | study plan | |||||

2019/2020 | (P0541D170006) Computational and Applied Mathematics | K | English | Ostrava | Choice-compulsory type B | study plan | |||||

2019/2020 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2019/2020 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2019/2020 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2019/2020 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2018/2019 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2018/2019 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2018/2019 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2018/2019 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2017/2018 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2017/2018 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2017/2018 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2017/2018 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2016/2017 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2016/2017 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2016/2017 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2016/2017 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2015/2016 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2015/2016 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1103V036) Computational and Applied Mathematics | K | English | Ostrava | Choice-compulsory | study plan | ||||

2015/2016 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | P | English | Ostrava | Choice-compulsory | study plan | ||||

2015/2016 | (P1807) Computer Science, Communication Technology and Applied Mathematics | (1801V001) Informatics | K | English | Ostrava | Choice-compulsory | study plan |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|