Wydział Matematyki i Nauk Informacyjnych
Politechnika Warszawska
prof. dr hab. inż. Władysław Homenda
Automata Theory and Formal Languages
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. MyhillNerode lemma, pumping lemma, applications. Grammars, direct derivation and derivation as relations, languages generated by grammars. Contextfree grammars, right and left derivations, derivation trees, uniqueness of words, grammars and languages. Left linear and right linear grammars, regular grammars.
 18 X 2019. Contextfree grammars, useless symbols, nullable symbols, unit productions. Normal forms of contextfree grammars: Chomsky and Greibach, transformation to Chomsky normal form.
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. MyhillNerode lemma, pumping lemma, examples. Grammars, definition, direct derivation, derivation, language generated. Left hand side and right hand side derivations.
 19 X 2018. Contextfree grammars, useless symbols, nullable symbols, unit productions.
 26 X 2018. Normal forms of contextfree grammars: Chmosky and Greibach, transformation to normal forms. Pumping lemma for contextfree languages.
 9 XI 2018. Pumping lemma for contextfree languages, proof, example. CYK algorithm.
 16 XI 2018. Contextsensitive and unrestricted grammars, contextsensitive and recursively enumerable languages. Normal form of contextsensitive grammars, a method of conversion to normal form, an example of contextsensitive 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 multitrack 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. Pushdown automata, summary. Finite automata deterministic and nondeterministic, configuration, move, computation, acceptation of input, language accepted.
 21 XII 2018. Finite automata with etransitions, configuration, move, computation. Equivalence of classes of finite automata deterministic, nondeterministic and with etransitions.
 4 I 2019. Equivalence of classes of finite automata and regular expressions, proof. Pumping lemma for regular languages, proof. MyhillNerode Theorem, proof.
 11 I 2019. Equivalence of classes of: context free grammars and pushdown 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 contextfree and contextsensitive 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, pushdown automata, finite automata.
 Nondeterminism, deterministic simulation
 Equivalence of regular expressions and finite automata, MyhillNerode 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/emini/en/course_details/305, 2010
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. 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 + (26F)*2. If S<26, the exercises are passed when F ≥ 26 + (26S)*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, the final grade is equal to 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.