Faculty of Mathematics and Information Science
Warsaw University of Technology
Professor Władysław Homenda
Automata Theory and Formal Languages
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
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.