Wydział Matematyki i Nauk Informacyjnych
Politechnika Warszawska
prof. nzw. dr hab. inż. Władysław Homenda
Automata Theory and Languages
Lectures, realization  fall 2017
 6 X 2017. Organization of the subject. Recalled topics: relations, equivalence relation and equivalence classes, right invariant relation, closure of relation, 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, regular languages.
 13 X 2017. MyhillNerode lemma, pumping lemma, examples. Grammars, definition, direct derivation, derivation, language generated. Left hand side and right hand side derivations, derivation trees.
 20 X 2017. Contextfree grammars, useless symbols, nullable symbols, unit productions, Chomsky and Greibach normal forms, transformations to normal forms.
 27 X 2017. Transformation to Greibach normal form cont. and Greibach normal forms. Pumping lemma, proof. CYK algorithm, example, homework: formulation of CYK algorithm.
 30 X 2017, 1416, 329. Pumping lemma for contextfree languages, example. Contextsensitive and unrestricted grammars, example of an unrestricted and contextsensitive grammar, homework: more unrestricted and contextsensitive grammars. Normal form of contextsensitive grammars, transformation of a contextsensitive grammar to normal form, proof.
 3 XI 2017. Turing machines, definition, interpretation, configuration, computation, example, basic model, model with guard, equivalence of both models.
 6 XI 2017, 1416, 329. Classes of Turing machines: multitrack, two ways infinite tape, multi tape. equivalence with the basic model class, cost of simulation of multi tape Turing machine.
 24 XI 2017. Multitape Turing machine  example. Nondeterministic Turing machines, computation, acceptance of input, equivalence of classes of deterministic and nondeterministic Turing machines (proof at next lecture).
 1 XII 2017. Simulation of nonodeterministic Turing machines with deterministic Turing machines. Linear bounded automata. Pushdown automata, definition, computation, conditions for determinism.
 15 XII 2017. Classes of pushdown automata accepting with final state and with empty input and empty stack, equivalence of both classes. Pushdown automata as restricted Turing machines. Finite automata deterministic and nondeterministic: definitions, graphs of automata, configuration, computation, acceptation of input, interpretation of nondeterminism as computation tree, closure of transition function, equivalence of transition function and closure of transition function on the domain of transition function.
 22 XII 2017. Finite automata with emoves. Equivalence of classes of automata deterministic, nondeteterministic and with emoves.
 5 I 2018. Equivalence of regular expressions and finite automata, proof. Pumping lemma for regular languages, proof. MPhilNerode Theorem, proof.
 12 I 2018. Operations on languages: union, intersection, complement, concatenation, Kleene closure, substitution, quotients. Closure of the class of regular languages wrt operations on languages, proof.
 19 I 2018. Equivalence of contextfree grammars and poshdown automata, construction of automata equivalent to grammars. Equivalence of contextsensitive grammars and linear bounded automata, equivalence of unrestricted grammars and Turing machines (without proofs). Closure of classes of contextfree, contextsensitive, recursive and recursively enumerated languages with regard to operations on languages, proofs.
 26 I 2018. Preliminary examination.
Tutorials, realization  fall 2017
Tutorial are conducted by dr inż. M. Luckner
Laboratories, realization  fall 2017
Laboratories are conducted by dr inż. M. Luckner, dr inż. Janusz Rafałko, dr inż. Agnieszka Jastrzębska, mgr inż. Aleksander Cisłak
Lectures, realization  fall 2016
 7 X 2016. Organization of the subject. Introductory information: alphabet, words over alphabet, languages over alphabet, canonical order, cardinality of the family of words and the family of languages. regular expressions, regular languages. Pumping lemma.
 14 X 2016. MyhillNerode lemma, examples. Grammars, definition, direct derivation, derivation, language generated. Regular grammars. Contextfree grammars, left hand side and right hand side derivations, derivation trees.
 21 X 2016. Simplification of contextfree grammars, useless symbols: methods of extraction, removing from the grammar, nullable symbols and productions, status change of nullable symbols and productions, unit productions, removing unit productions.
 28 X 2016. Chomsky and Greibach normal forms of contextfree grammars, methods of transformation, pumping lemma with proof.
 4 XI 2016. Checking whether word is generated by contextfree grammar: algorithm and its complexity for Greibach norma form, algorithm CYK (formulation of CYK algorithm as homework) and its complexity for Chomsky normal form.
 10 XI 2016. Contextsensitive grammars and languages, normal form of contextsensitive grammars. Unrestricted grammars and recursively enumerable languages.
 17 XI 2016. Turing machine, definition, interpretation of basic model. Example of Turing machine computing function ceiling(n/3), computation of Turing machine, stop property, acceptation of languages. Model with guard, equivalence of machines with guard and in basic model.
 25 XI 2016. Turing machine, models with multi tracks tape, two way infinite tape, multi tape, equivalence of models, cost of simulation.
 2 XII 2016. Nondeterministic Turing machine, computation, input acceptance, equivalence of classes of deterministic and nondeterministic Turing machines, cost of deterministic simulation.
 9 XII 2016. Linear bounded automata  definition, pushdown automata, transition function, configuration, computation, input acceptance, determinism, acceptance with accepting state and with empty input and empty stack, equivalence of both types of acceptance, push down automata as restricted Turing machines.
 16 XII 2016. Finite deterministic and nondeterministic automata  definitions, transition functions, configuration, computation, input acceptance, closure of transition function, equivalence of classes of deterministic and nondeterministic automata.
 21 XII 2016. Finite automata with emoves  definitions, transition functions, configuration, computation, input acceptance, closure of transition function, equivalence of classes of automata with emoves and nondeterministic automata.
 13 I 2017. Equivalence of classes of finite automata and regular expressions. Closure/nonclosure of the class of contextfree languages under union, intersection, complement, concatenation, Kleene closure.
 20 I 2017. Equivalence of classes of Turing machines and unrestricted grammars. Closure/nonclosure of the class of recursively enumerable languages under union, intersection, complement, concatenation, Kleene closure, diagonal language, universal language.
 27 I 2017. Equivalence of classes of linear bounded automata and contextsensitive grammars. Closure/nonclosure of the class of contextsensitive languages under concatenation and Kleene closure cont., diagonal language in the class of contextsensitive languages, strict inclusions of the class of contextfree languages in the class of recursive languages.
Tutorials, realization  fall 2016
Tutorial are conducted by dr inż. M. Luckner
Laboratories, realization  fall 2016
Laboratories are conducted by dr inż. M. Luckner, dr inż. Janusz Rafałko, mgr inż. Aleksander Cisłak
Lectures, realization  fall 2015
 2 X 2015. Organization of the subject. Revisions: mathematical induction, trees  inductive definition, lemma  number of leaves in ktree, relations, equivalence relations. Introductory information: alphabet, words over alphabet, languages over alphabet, cardinality of family of words and family of languages, relations induced by language and right invariant relations.
 9 X 2015. Regular expressions, regular languages, MyhillNerode lemma, pumping lemma.
 16 X 2015. Grammars, derivation, language accepted. Regular grammars. Contextfree grammars, left and right derivations, derivation trees, useless symbols: methods of extraction, removing from the grammar.
 30 X 2015. Nullable symbols and productions, unit productiona. Chomsky and Greibach normal forms.
 30 X 2015, 46PM (instead of canceled lecture on October 23rd). Pumping lemma, CYK algorithm.
 6 XI 2015. Contextsensitive grammars, normal form, example. Unrestricted grammars. Chomsky hierarchy. Turing machine, definition, interpretation of basic model.
 20 XI 2015. Example of Turing machine computing function ceiling(n/3), computation of Turing machine, stop property, acceptation of languages. Model with guard, equivalence of machines with guard and in basic model.
 27 XI 2015. Turing machines with two way infinite tape and multitude. Equivalence of classes of two way infinite tape machines and machines in basic model, equivalence of classes of multitape machines and machines in basic model.
 4 XII 2015. Nondeterministic Turing machines, computation, examples, equivalence of classes of deterministic and nondeterministic Turing machines.
 11 XII 2015. Pushdown automata, definition, configuration, computation, examples, conditions for determinism, equivalence of acceptation with accepting state and with empty input and stack.
 18 XII 2015. Finite automata, deterministic and nondeterministic, configuration, computation, acceptation of input data, closure of transition function.
 8 I 2015. Equivalence of the classes of finite automata (deterministic, nondeterministic, with etransitions).
 15 I 2016. Equivalence of the class of finite automata and the class of regular expressions. Substitution, homomorphism, quotients of languages, definitions examples. Closeness of the class of regular languages with respect to operations on languages: union, intersection, complement, concatenation, Kleene closure  with proofs, substitution, homomorphism and quotients  without proofs.
 22 I 2016. Pumping lemma for regular languages and MyhillNerode Theorem  proofs.
 29 I 2016. Closeness of classes of contextfree and contextsensitive languages with regards to union, intersection, complement, concatenation, Kleene closure, substitution.
Tutorials, realization  fall 2015
Tutorial are conducted by dr inż. M. Luckner
Lectures, realization  fall 2014
 3 X 2014. Organization of the subject. Introductory information: alphabet, words over alphabet, languages over alphabet, operations over alphabet, relations induced by language and right invariant relations. Regular expressions, tbc.
 10 X 2014. Regular expressions (cont.), regular languages, pumping lemma, MyhillNerode lemma. Grammars, regular grammars.
 17 X 2014. Contextfree grammars, left and right hand side derivations, derivation trees, grammars ambiguity, useless symbols, nullable symbols and productions, unit productions, grammars simplifications, Chomsky and Greibach normal forms, CYK algorithm.
 24 X 2014. Pumping lemma for contextfree languages, Ogden lemma, the idea of proof, applying. Greibach normal form, conversion of contextfree grammars to this form.
 31 X 2014. Contextsensitive and unrestricted grammars, normal form of contextsensitive grammars, examples of contextsensitive and unrestricted grammars. Chomsky hierarchy.
 14 XI 2014. Turing machines, configuration, computation, example. Models of Turing machines and their equivalence: basic, with guard, with multitrack tape, two ways infinite tape.
 21 XI 2014. Multitape Turing machines, equivalence of classes of multitape and onetape machines, cost of onetape simulation. Nondeterministic Turing machines, acceptation of input, computation, interpretation of nondeterminism.
 24 XI 2014. Equivalence of the class of nondeterministic Turining machines and the class of deterministic Turing machines, cost of deterministic simulation, liniear bounded automata.
 28 XI 2014. Pushdown automata, configuration, computation, determninizm, acceptation with accepting states and with empty stack and empty input, pushdown automata as Turing machines.
 5 XII 2014. Deterministic, nondeterministic and with emoves finite automata, configuration, computation, acceptation of input, extension of transition function to words  intuitive introduction.
 15 XII 2014. Equivalence of classes of deterministic, nondeterministic and with etransitions finite automata. Equivalence of classes regular expressions and finite automata.
 19 XII 2014. Proof of pumping lemma for regular languages, MyhillNerode theorem with proof. Closeness of classes of regular, contextfree and contextsensitive languages with regard to operations on languages.
 16 I 2015. Closeness of classes of recursive and recursively enumerable clases of languages with regard to: union, intersection, complement, concatenation, Kleene closure, universal and diagonal languages.
 23 I 2015. Substitution and homomorphism, quotients (tutorials). Closeness of classes of languages with regard to substitution and homomorphism.
 30 I 2015. Consultations before exam.
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 / 2 / 0 / 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 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.