N_AG Automata and Grammars

University of Finance and Administration
Winter 2022
Extent and Intensity
2/1/0. 6 credit(s). Type of Completion: zk (examination).
Guaranteed by
RNDr. Petr Tesař, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ivana Plačková
Prerequisites
There are no prerequisites for this course.
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives
The aim of the subject is to acquaint students with the problems of finite automata and formal languages. Increased attention is paid to context-free grammars because practically all programming computer languages ​​are defined using context-free grammars. When translating program source texts, the properties of context-free grammars are used in conjunction with stack automata.
Learning outcomes
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 solutions.
Syllabus
  • 1) Introduction. The concepts of set theory. Definition of finite automaton. Representations of finite automata.
  • 2) Languages recognizable by finite automata. Nerode theorem. Criteria for the design of a finite automaton.
  • 3) Definition of non-deterministic finite automata. Relationship languages recognizable by non-deterministic finite automaton and recognizable by deterministic finite automaton. Definition of generalized non-deterministic finite automata. Relationship languages recognizable by generalized non-deterministic finite automaton and recognizable by finite automaton.
  • 4) Set operations with languages, intersection, complement, difference, product (concatenation), left / right quotient language by another language, left / right derivation by words. Substitution of language non-discharging substitution of language, homomorphism, non-discharging homomorphism. Closure properties of the class of languages recognizable by finite automata in respect of certain operations by the set. Definition of regular languages over a finite alphabet. Relationship regular languages and finite automata - Kleene theorem.
  • 5) Definition of rewriting system. The concept of succession was derived (or derivatives) of length n words from the word u. Definition of generative grammar, nonterminal, terminal, rewriting rules, language generated generative grammar. Definition of analytic grammar and its relation to generative grammar. Chomsky hierarchy (and their generated languages).
  • 6) Definition of non-discharging context-free grammars and the relationship with the context-free grammar. The relationship between languages recognizable by a finite automaton languages and Type 3 according to Chomsky. Definition of left-linear grammar and relationship to grammars of Type 3 Definition of linear grammar. The relationship between regular languages and the class of linear languages.
  • 7) Reduced grammar. The canonical derivation, derivation trees, unambiguous grammar. Parsing analysis Top-down.
  • 8) Pushdown automata and context-free grammars. Parsing analysis Bottom-up. Chomsky normal form, Greibach normal form.
  • 9) Definition simple LL(1) grammar. Definition of LL(1) parser. Relationship LL(1) grammar LL(1) parser.
  • 10) The definition of LR (0) grammar. Relationship LR (0) grammars and deterministic pushdown automata.
  • 11) Definition of Turing Machine (abbreviation TM). TM configurations. Initial configuration of the TM, immediately following the TM configuration and final configuration of TM. TM recognition language. The relationship between language and the languages recognizable TM Type 0.
  • 12) Definition of recursive language. Definition of recursively countable language. The relationship between recursive languages and recursively countable languages - Post theorem.
Literature
    required literature
  • M. Chytil: Automaty a gramatiky, Praha, SNTL, 1984
Teaching methods
Lectures, examples.
Assessment methods
The course ends with an oral examination. Oral exam consists of one question. Range of issues covering the entire presentation area. The exam is admitted only students who had obtained credit from subject N_AG. To obtain the credit is necessary in the written test consisting of 3 examples acquire at least 50% of the points.
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: 16 hodin KS/semestr.
The course is also listed under the following terms Winter 2014, Winter 2015, Winter 2016, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2022, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/winter2022/N_AG