## Automata Theory and Formal Languages

### Lectures, realization - fall 2022

- 5 X 2022. Organization of the subject. Introductory notions: an alphabet, words over alphabet, the set of all words over alphabet, canonical order, cardinality of the set of all words, languages over alphabet, cardinality of the family of languages. Grammars, derivations, the languge generated by a grammar.
- 12 X 2022.Operations on languages: union, intersection, complement, concatenation, Kleene closure. Right invariant relation, relation induced by a language introduced in tutorials. Regular expressions. Languages generated by regular expressions. Equivalence of regular expressions. Regular languages, Myhill-Nerode lemma, pumping lemma.
- 19 X 2022.Myhill-Nerode lemma, pumping lemma - applications. Context-free grammars, derivation trees, ambiguity of words derivation, ambiguity of grammars and languages, useless symbols - identification and removal.
- 26 X 2022. Simplification of context free grammars: nullable symbols, unit productions. Chomsky normal form and Greibach normal form, grammars transformation to normal forms.
- 2 XI 2022. Pumping lemma for context-free languages: formulation, proof, application. Cocke-Younger-Kasami algorithm.
- 16 XI 2022. Context-sensitive and unrestricted grammars, context-sensitive and recursively enumerable languages. Normal form of context-sensitive grammars, a method of conversion to normal form, an example of context-sensitive grammar.
- 23 XI 2022. Turing machines, basic model.
- 30 XI 2022. Turing machines: modification of basic model, machines with multitrack tape and their equivalence with machines in basic model, multitape Turing machines.

### Tutorials, realization - fall 2022

Tutorial are conducted by dr inż. M. Luckner

### Lectures, realization - fall 2021

- 6 X 2021. Organization of the subject. Revision: mathematical induction, inductive definition of trees, k-trees, number of leaves. Introductory notions: an alphabet, words over alphabet, the set of all words over alphabet, canonical order, cardinality of the set of all words, languages over alphabet, cardinality of the family of languages. Grammars, derivations, the languge generated by a grammar.
- 13 X 2021. Regular grammars. Operations on languages: union, intersection, complement, concatenation, Kleene closure. Right invariant relation, relation induced by a language (defined in tutorials). Regular expressions. Languages generated by regular expressions.
- 20 X 2021. Regular languages, Myhill-Nerode lemma, pumping lemma, applications. Context-free grammars, useless symbols.
- 27 X 2021. Context-free grammars, unit productions, nullable symbols, nullable production. Simplification of grammars: elimination of useless symbols, unit productions, nullable symbols/productions.
- 3 XI 2021. Chomsky and Greibach normal forms.
- 17 XI 2021. Pumping lemma, proof and application of contrapositive. Cocke-Younger-Kasami algorithm, application: membershipness, derivation trees.
- 24 XI 2021. Applications of context-free grammars: grammars with translation, LL(1) grammars, a grammar generating arithmetcial expressions and their suffix form (reverse Polish notation). The material of this lecture is not required for the final exam.
- 8 XII 2021. Turing machines: definition, interpretation, configuration, computation, an example of Turing machine and its computation.
- 11 XII 2021. Models of Turing machines: with guard, with simplified/unified stop condition, with multitrack tape, with two way infinite tape.
- 15 XII 2021. Nondeterministic Turing machines.
- 22 XII 2021. Push-down automata, definition, configuation, computation, examples.
- 5 I 2022. Push-down automata, determinizm, accepting with accepting states and with empty input and stack, push-down automata as limited Turing machines. Equivalence of classes of push-down automata and context-free grammars.
- 12 I 2022. Closure of the class of context-free languages due to operations on languages. Strict inclusion of the class of context-free languages in the class of context-sensitive languages.
- 19 I 2022. Pumping lemma for regular languages, Myhill-Nerode Theorem, proofs.
- 26 I 2022. Closure of the class of regular languages due to operation on languages. Strict inclusione og the class of context-sensitive languages in the class of recursive languages

### Tutorials, realization - fall 2021

Tutorial are conducted by dr inż. M. Luckner and dr inż. Janusz Rafałko

### Lectures, realization - fall 2020

- 7 X 2020. Organization of the subject. Introductory notions: an alphabet, words over alphabet, the set of all words over alphabet, canonical order, cardinality of the set of all words, languages over alphabet, cardinality of the set of the family of languages, operations on languages: union, intersection, complement, concatenation, Kleene closure, right invariant relation, relation induced by a language. Regular expressions.
- 14 X 2020. Languages generated by regular expressions. Myhill-Nerode lemma, pumping lemma, applications. Grammars.
- 21 X 2020. Derivation, words and languages generated by grammars. Left and right linear grammars, regular grammars - only definitions. Context-free grammars, derivations, derivation trees, useless symbols (non generating, unobtainable), identification of useless symbols, grammars simplification by deleting useless symbols and corresponding productions.
- 28 X 2020. Context-free grammars, nullable symbols, unit productions. Normal forms of context-free grammars: Chomsky and Greibach, transformation to Chomsky normal form.
- 4 XI 2020. Transformation to Greibach normal form, idea of proof. Pumping lemma for context-free languages, proof.
- 13 XI 2020. CYK algorithm, example.
- 18 XI 2020. Context-sensitive and unrestricted grammars, context-sensitive and recursively enumerable languages. Normal form of context-sensitive grammars, a method of conversion to normal form, an example of context-sensitive grammar.
- 25 XI 2020. Turing machines, definition, interpretation, configuration, computation, example, basic model.
- 2 XII 2020. Turing machines: with guard, with multitrack tape, with two ways infinite tape, equivalence justifications of models.
- 9 XII 2020. Push down automata, simple model, configuration, computation, basic model, nondeterminism. Nondeterministic push-down automata, computation and its interpretation (computation tree), conditions for determinism of basic model, acceptation by accepting state and by empty input and empty stack.
- 16 XII 2020. Nondeterministic Turing machines, equivalence of classes of deterministic and nondeterministic Turing machines - proof, cost of deterministic simulation.
- 23 XII 2020. Finite automata: deterministic, nondeterministic, with e-transitions; configuration, computation, computation tree, generalised transition function, examples.
- 13 I 2021. Pumping Lemma, proof. Myhill-Nerode Theorem, proof, minimal deterministic automata. Closure of the class of regular languages under union, complement, intersection, concatenation, Kleene closure.
- 20 I 2021. Equivalence of classes: of context free grammars and push-down automata, context sensitive grammars and linear bounded automata. Operation of substitution. Closure of the class of context-free and context-sensitive languages under operations on them.
- 27 I 2021. Membership of context-sensitive languages. Chomsky hierarchy, encoding of grammars, diagonal language in the class of context-sensitive languages, strict inclusion of the class of context-sensitive languages in the class of recursive languages, proof.

### Tutorials, realization - fall 2020

Tutorial are conducted by dr inż. M. Luckner and dr inż. Agnieszka Jastrzębska

### Lectures, realization - fall 2019

- 4 X 2019. Organization of the subject. Introductory notions: an alphabet, words over alphabet, the set of all words over alphabet, canonical order, cardinality of the set of all words, languages over alphabet, cardinality of the set of the family of languages, operations on languages: union, intersection, complement, concatenation, Kleene closure, right invariant relation, relation induced by a language. Regular expressions, languages generated by regular expressions.
- 11 X 2019. Myhill-Nerode lemma, pumping lemma, applications. Grammars, direct derivation and derivation as relations, languages generated by grammars. Context-free grammars, right and left derivations, derivation trees, uniqueness of words, grammars and languages. Left linear and right linear grammars, regular grammars.
- 18 X 2019. Context-free grammars, useless symbols, nullable symbols, unit productions. Normal forms of context-free grammars: Chomsky and Greibach, transformation to Chomsky normal form.
- 25 XI 2019. Transformation to Greibach normal form. Pumping lemma for context-free languages, proof. CYK algorithm, example.
- 8 XI 2019. Pumping lemma for context-free languages, example. Context-free grammar, example. Nullable productions. Transformation to Chomsky and Greibach normal forms.
- 15 XI 2019. Context-sensitive and unrestricted grammars, context-sensitive and recursively enumerable languages. Normal form of context-sensitive grammars, a method of conversion to normal form, an example of context-sensitive grammar.
- 22 XI 2019. Turing machines, definition, interpretation, configuration, computation, example, basic model, model with guard, with multi-track tape, equivalence of models.
- 29 XI 2019. Turing machines, models and their equivalence: two ways infinite tape, multi tape, proofs of equivalence, cost of simulation.
- 6 XII 2019. Nondeterministic Turing machines, equivalence of classes of deterministic and nondeterministic Turing machines - proof, cost of deterministic simulation, example - two tape nondeterministic Turing machine accepting binary words of the form ww. Linear bounded automata, definitions and their equivalence.
- 13 XII 2019. Push-down automata, configuration, move, e-transitions, computation, language accepted, determinizm, equivalence of automata accepting with final states and with empty input and stack, examples: automaton accepting binary words 0's not dominating 1's in each prefix, automaton accepting binary palindromes of even length.
- 20 XII 2019. Finite automata deterministic and nondeterministic, configuration, transition, computation, acceptation of input, language accepted. Equivalence of classes of finite automata deterministic and nondeterministic. Automata with with e-transitions, computation. Equivalence of classes of finite automata with e-transitions and nondeterministic, to be continued.
- 10 I 2020. Equivalence of classes of finite automata with e-transitions and nondeterministic, example. Equivalence of classes of finite automata and regular expressions, proof. Pumping lemma for regular languages, proof. Myhill-Nerode Theorem.
- 17 I 2020. Myhill-Nerode Theorem, proof, minimal deterministic automata. Operations on languages, substitution, homomorphism. Closure of the class of regular languages under operations on them.
- 24 I 2020. Equivalence of classes of: context free grammars and push-down automata, context sensitive grammars and linear bounded automata. Closure of the class of context-free and context-sensitive languages under operations on them. Chomsky hierarchy, justification of initial inclusions.
- 31 I 2020. Chomsky hierarchy, strict inclusion of the class of context-sensitive languages in the class of recursive languages, proof. Closure of the class of recursive languages under operations on them.

### Tutorials, realization - fall 2019

Tutorial are conducted by dr inż. M. Luckner and dr inż. Agnieszka Jastrzębska

### Lectures, realization - fall 2018

- 5 X 2018. Organization of the subject. Recalled topics: mathematical induction, inductive definition of a tree, relation between height of a tree and number of leaves. Introductory notions: an alphabet, words over alphabet, languages over alphabet, canonical order, cardinality of the set of all words and the family of languages, operations on languages: union, intersection, complement, concatenation, Kleene closure, relation induced by a language. Regular expressions.
- 12 X 2018. Regular languages. Myhill-Nerode lemma, pumping lemma, examples. Grammars, definition, direct derivation, derivation, language generated. Left hand side and right hand side derivations.
- 19 X 2018. Context-free grammars, useless symbols, nullable symbols, unit productions.
- 26 X 2018. Normal forms of context-free grammars: Chmosky and Greibach, transformation to normal forms. Pumping lemma for context-free languages.
- 9 XI 2018. Pumping lemma for context-free languages, proof, example. CYK algorithm.
- 16 XI 2018. Context-sensitive and unrestricted grammars, context-sensitive and recursively enumerable languages. Normal form of context-sensitive grammars, a method of conversion to normal form, an example of context-sensitive grammar.
- 23 XI 2018. Turing machines, definition, interpretation, configuration, computation, example, basic model, model with guard, equivalence of both models.
- 30 XI 2018. Turing machines, models and their equivalence: with multi-track tape, with two ways infinite tape, multi tape (proof moved to next lecture).
- 7 XII 2018. Multi tape Turing machines, proof of equivalence. Nondeterministic Turing machines, equivalence of classes of deterministic and nondeterministic Turing machines, proof.
- 14 XII 2018. Push-down automata, summary. Finite automata deterministic and nondeterministic, configuration, move, computation, acceptation of input, language accepted.
- 21 XII 2018. Finite automata with e-transitions, configuration, move, computation. Equivalence of classes of finite automata deterministic, nondeterministic and with e-transitions.
- 4 I 2019. Equivalence of classes of finite automata and regular expressions, proof. Pumping lemma for regular languages, proof. Myhill-Nerode Theorem, proof.
- 11 I 2019. Equivalence of classes of: context free grammars and push-down automata, context sensitive grammars and linear bounded automata, unrestricted grammars and Turing machines, proofs. Chomsky hierarchy (extend), justification of inclusions. Turing machines encoding.
- 18 I 2019. Diagonal language and universal language and their place in Chomsky hierarchy, proofs. Closure of the class of regular languages under operations on languages, proofs.
- 25 I 2019. Closure of the classes of context-free and context-sensitive languages under operations on languages, proofs.

### Tutorials, realization - fall 2018

Tutorial are conducted by dr inż. M. Luckner and mgr inż. Aleksander Cisłak

### Laboratories, realization - fall 2018

Laboratories are conducted by dr inż. M. Luckner, dr inż. Janusz Rafałko, mgr inż. Aleksander Cisłak

## Course description:

Course title |
Automata Theory and Languages |

Program |
BSc |

Status of the Course: |
compulsory |

Responsible person: |
Władysław Homenda, PhD, DSc |

Hours per week, assessment method |
2 / 1 / 1 / 0 / E |

Internal code no |
---- |

### Lectures:

- Regular expressions, context free, context sensitive and unlimited grammars, pumping lemmas, Ogden lemma.
- Turing machines, push-down automata, finite automata.
- Nondeterminism, deterministic simulation
- Equivalence of regular expressions and finite automata, Myhill-Nerode theorem
- Equivalence of push down automata and context free languages.
- Equivalence of Turing machines and recursively enumerable languages.
- Chomsky hierarchy.

### Reference books:

- Introduction to automata theory, languagies and computation, Hopcrpft J, Ullman J., PWN 1994.
- Elementy lingwistykim matematycznej i teorii automatow, W. Homenda, WPW, 2005
- Formal languages and automata, Lecture Notes and Problems, W. Homenda, https://gamma.mini.pw.edu.pl/e-mini/en/course_details/305, 2010
- W. Homenda, W. Pedrycz, Automata Theory and Formal Languages, De Gruyter

### Required prerequisites:

Algorithms and data structures

Introduction to logic and set theory

### Regulations and assessment method (October 12th, 2019):

- The course “Automata Theory and Formal Languages” is composed of lectures (30h) and tutorials (30h). Attendance is not obligatory.
- The grade for the course must be obtained in the current academic year by following the rules outlined below. There is no option to consider any scores/grades/points/etc. obtained in the past.
- During the tutorials there will be two written tests that will check student’s knowledge of theory and her/his ability to solve practical exercises. The first test is scheduled for the 7th meeting. The second test is scheduled for the 15th meeting. Each test allows to score between 0 and 50 points. During these two tests it is allowed to have an A5 page with handwritten notes. It cannot be a copy of somebody else’s notes.
- During tutorials there will be a chance to get extra points for solving assignments at the blackboard. It is possible to obtain up to 10 extra points between the 1st and the 6th class. It is possible to obtain up to 10 extra points between the 8th and the 14th class.
- The number of points from the first test is added to the number of extra points achieved between the 1st and the 6th class. Let us denote this sum as F. The number of points from the second test is added to the number of extra points achieved between the 8th and the 15th class. Let us denote this sum as S.
- After the exercises are finished (that is after January 31st), there will be an obligatory exam composed of two parts: theoretical and practical. During the practical part of the exam it is allowed to have an A5 page with handwritten notes. It cannot be a copy of somebody else’s notes. No aids are allowed for the theoretical part. Both theoretical and practical part must be passed on the same day to pass the course.
- The Dean’s Office schedules the exam. The number of dates and the allowed number of attempts that a student can take at the exam are regulated by the official “Rules of Study” of the Warsaw University of Technology.
- Approximately 40% of students that will achieve best score (F+S) will be exempted one time from the practical part of the exam, when taking the exam for the first time. In this case, (F+S) will be assumed as the percentage score of the practical part of the exam. The exemption is not compulsory: if a student is not satisfied with her/his score, (s)he does not have to take the exemption. In the case, if a student takes the exemption, but does not pass the theoretical part on the day when (s)he took the exemption, (s)he cannot get the exemption again. In order to get the exemption, it is necessary to have F>25 and S>25 (and be among the students with the best score). If F<26, the exercises are passed when S ≥ 26 + (26-F)*2. If S<26, the exercises are passed when F ≥ 26 + (26-S)*2.
- A student can get a grade from the set {2, 3, 3.5, 4, 4.5, 5} separately from the theoretical and practical part of the exam. Grade 2 means that the given part was not passed. To pass the exam both grades must be obtained the same day, and both must be greater than 2. The final course grade is computed as the average of the two grades. If the two grades (from the theoretical and the practical part) will differ by 0.5 or 1.5, the final grade is equal to the mean from both grades rounded towards the grade from the theoretical part of the exam.

### Assessment method (October 18th, 2015):

- required is completing both practical and theoretical parts of exam (i.e. to earn more than 50% points for each part), both parts have form of written test, both must be completed in same date set by the dean office, two dates are set in February, one in September,
- one can enjoy exemption from practical part by completing laboratory tests, exemption can be used only once at one's first attempt to exam,
- final grade is equal to mean of grades of practice and theory, grades of each part reflect usual scale: C for >50% points, C+ for >60% points etc.
- allowed is A5 sheet of paper with handwritten help (no printing, no photocopying) at practical tests, no help is permitted at theoretical test.

### Assessment method (October 1st, 2015):

- required is completing practical and theoretical parts of the subject, both must be completed in current academic year,
- practical part can be passed a) by completing laboratory tests, b) at first date of exam,
- passing practice is necessary before taking theory, theory can be taken in dates set by the dean office (two dates in February, one in September),
- assessment of the theory part is the grade of the first attempt or 2 and the grade of the second attempt or 2, 2 and the grade computed as max(2,floor(o3)-1), where o3 is the grade of the third attempt (October 5th, 2015),
- final grade is equal to mean of assessments of practice and theory,
- allowed is A5 sheet of paper with handwritten help (no printing, no photocopying) at practical tests, no help is permitted at theoretical test.