N_AG Automata and Grammars

University of Finance and Administration
Winter 2015
Extent and Intensity
2/1. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
RNDr. Michal Žemlička, Ph.D. (seminar tutor)
RNDr. Petr Tesař, Ph.D. (assistant)
Guaranteed by
RNDr. Michal Žemlička, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ing. Barbora Ptáčková
Timetable of Seminar Groups
N_AG/vAPH: Sat 24. 10. 11:30–13:00 S11, 14:00–15:30 S14, Sat 7. 11. 14:00–15:30 S11, Sat 5. 12. 9:45–11:15 S11, 11:30–13:00 S11, Sat 9. 1. 11:30–13:00 E227, M. Žemlička
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives
The students will be able, at the end of this course, to use autmata and grammars as formal tools for software specidfiction, description and modeling. Knowledge and skills acquired within this course will allow the student (in many cases) to recognize the complexity of the task and to search for proper tools.
Syllabus
  • 1) introduction; notions, notation
  • 2) autamata, grammars, and formal languages and their relationships
  • 3) finite automata; NFS, DFA
  • 4) regular languages, regular grammars
  • 5) context-free grammars, context-free languages
  • 6) pushdown automata
  • 7) deterministic context-free languages, LL and LR analysis
  • 8) context-sensitive languages, context-sensitive grammars, examples
  • 9) general formal languages, Turing Machine
  • 10) tranducers
  • 11) languages, automata and complexity
  • 12) related tools (flex, bison, ...); examples
Literature
    required literature
  • M. Chytil: Automaty a gramatiky, Praha, SNTL, 1984
Teaching methods
Lectures, examples, using tools.
Assessment methods
Written test with a few exmples and theoreticla problems to solve.
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
Information on the extent and intensity of the course: 12 hodin KS/semestr.
The course is also listed under the following terms Winter 2014, Winter 2016, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2015, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/winter2015/N_AG