Automata Theory and Formal Languages

Lectures, realization - fall 2023

1. 4 X 2023. 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. Right invariant relation, relation induced by a language.
2. 11 X 2023. Relation induced by a language, supplement. Regular expressions. Languages generated by regular expressions. Equivalence of regular expressions. Regular languages, Myhill-Nerode lemma, pumping lemma.
3. 18 X 2023. 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.
4. 25 X 2023. Simplification of context free grammars: nullable symbols, unit productions. Chomsky normal form and Greibach normal form, grammars transformation to normal forms.
5. 8 XI 2023. Cocke-Younger-Kasami algorithm. Pumping lemma for context-free languages, Ogden lemma: formulation, proof.
6. 15 XI 2023. Pumping lemma for context-free languages, example. Not required for tests and exam: grammars with translation, LL(1) grammars, LL(1) grmmar with translation converting arithmetical expressions to posfix notation.
7. 22 XI 2023. 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.
8. 20 XII 2023. Turing machines, linear bounded automata.
9. 3 I 2024. Equivalence of Turing machines and unrestricted grammars. Classes of recursive and recursively enumerated languages. Diagonal and universal languages and their complements.
10. 5 I 2024. Equivalence of linear bounded automata and context-sensitive grammars. Classes of context-sensitive and recursive languages, diagonal language in the class of context-sensitive languages.
11. 10 I 2024. Equivalence of push-down automata and context-free grammars. Finite automata: deterministic, nondeterministic and with e-moves.
12. 10 I 2024. Equivalence of classes of deterministic, nondeterministic and with e-moves. Closure of tramsition function.
13. 12 I 2024. Equivalence of classes of finite automata, regular expressions and regular grammars. Pumping lemma for regular languages, proof.
14. 17 I 2024. Class closure of regular and context-free languages due to language operations (union, intersection, complement, concatenation, star closure. Myhill-Nerode Theorem.
15. 24 I 2024. Zero term exam.

Tutorials, realization - fall 2023

Tutorial are conducted by dr hab. inż. M. Luckner

Lectures, realization - fall 2022

1. 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.
2. 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.
3. 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.
4. 26 X 2022. Simplification of context free grammars: nullable symbols, unit productions. Chomsky normal form and Greibach normal form, grammars transformation to normal forms.
5. 2 XI 2022. Pumping lemma for context-free languages: formulation, proof, application. Cocke-Younger-Kasami algorithm.
6. 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.
7. 23 XI 2022. Turing machines, basic model.
8. 30 XI 2022. Turing machines: modification of basic model, machines with multitrack tape and their equivalence with machines in basic model, multitape Turing machines.
9. 7 XII 2022. Multitape Turing machines - equivalence with one tape Turing machines. Nondeterministic Turing machines.
10. 10 XII 2022. Equivalence of classes of nondeterministic and deterministic Turing machines, cost of deterministic simulation. Linear bounded automata. Push-down automata, definition, configuation, computation, examples.
11. 21 XII 2022. Push-down automata, determinizm, accepting with accepting states and with empty input and stack, push-down automata as limited Turing machines. Deterministic finite automata, definition, configuration, computation, examples.
12. 4 I 2023. Nondeterministic finite automata, definition, configuration, computation, examples. Equivalence of classes of deterministic and nondeterministic finite automata. Finite automata wirh e-moves, definition, e-closure, configuration, computation, examples.
13. 11 I 2023. Equivalence of classes of regular expressions and finite automata. Pumping lemma for regular languages, Myhill-Nerode Theorem, proofs. Minimal deterministic automata.
14. 18 I 2023. Equivalence of classes of context-free grammars and push-down automata, context-sensitive grammars and linear bounded automata, unrestricted grammars and Turing machines. Substitiution and homomorphism. Class closure of regular and context-free languages due to language operations.

Tutorials, realization - fall 2022

Tutorial are conducted by dr inż. M. Luckner

Course description:

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, pp. 1-231, 2022.

Required prerequisites:

Algorithms and data structures
Introduction to logic and set theory

Regulations and assessment method (since fall semester 2023/24):

• 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.
• After the tutorials are finished (that is after late January), 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 30% - 50% of students that pass tutorials and will achieve best score will be exempted one time from the practical part of the exam, when taking the exam for the first time. In this case, the score from tutorials will be assumed as the 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.
• 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.

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.