Your browser doesn't support this content. You can turn it off by clicking on/off icon on the footer area of the page.


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. Myhill-Nerode lemma, pumping lemma, examples. Grammars, definition, direct derivation, derivation, language generated. Left hand side and right hand side derivations, derivation trees.
  • 20 X 2017. Context-free 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, 14-16, 329. Pumping lemma for context-free languages, example. Context-sensitive and unrestricted grammars, example of an unrestricted and context-sensitive grammar, homework: more unrestricted and context-sensitive grammars. Normal form of context-sensitive grammars, transformation of a context-sensitive 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, 14-16, 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.
  • 1 XII 2017.
  • 15 XII 2017.
  • 22 XII 2017.
  • 5 I 2018.
  • 12 I 2018.
  • 19 I 2018.
  • 26 I 2018.

Tutorials, realization - fall 2017

Tutorial are conducted by dr inż. Marcin Luckner, dr inż. Janusz Rafałko and mgr inż. Aleksander Cisłak.


Laboratories, realization - fall 2017

Tutorial are conducted by dr inż. Marcin Luckner, dr inż. Janusz Rafałko and 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. Myhill-Nerode lemma, examples. Grammars, definition, direct derivation, derivation, language generated. Regular grammars. Context-free grammars, left hand side and right hand side derivations, derivation trees.
  • 21 X 2016. Simplification of context-free 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 context-free grammars, methods of transformation, pumping lemma with proof.
  • 4 XI 2016. Checking whether word is generated by context-free 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. Context-sensitive grammars and languages, normal form of context-sensitive 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, push-down 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 e-moves - definitions, transition functions, configuration, computation, input acceptance, closure of transition function, equivalence of classes of automata with e-moves and nondeterministic automata.
  • 13 I 2017. Equivalence of classes of finite automata and regular expressions. Closure/nonclosure of the class of context-free 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 context-sensitive grammars. Closure/nonclosure of the class of context-sensitive languages under concatenation and Kleene closure cont., diagonal language in the class of context-sensitive languages, strict inclusions of the class of context-free languages in the class of recursive languages.

Tutorials, realization - fall 2016

Tutorial are conducted by dr inż. Marcin Luckner


Laboratories, realization - fall 2016

Laboratories are conducted by dr inż. Marcin Luckner, dr inż. Janusz Rafałko and 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 k-tree, 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, Myhill-Nerode lemma, pumping lemma.
  • 16 X 2015. Grammars, derivation, language accepted. Regular grammars. Context-free 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, 4-6PM (instead of canceled lecture on October 23rd). Pumping lemma, CYK algorithm.
  • 6 XI 2015. Context-sensitive 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. Push-down 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 e-transitions).
  • 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 Myhill-Nerode Theorem - proofs.
  • 29 I 2016. Closeness of classes of context-free and context-sensitive languages with regards to union, intersection, complement, concatenation, Kleene closure, substitution.

Tutorials, realization - fall 2015

Information about tutorials at dr inż. M. Luckner's web page.
 


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, Myhill-Nerode lemma. Grammars, regular grammars.
  • 17 X 2014. Context-free 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 context-free languages, Ogden lemma, the idea of proof, applying. Greibach normal form, conversion of context-free grammars to this form.
  • 31 X 2014. Context-sensitive and unrestricted grammars, normal form of context-sensitive grammars, examples of context-sensitive 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. Multi-tape Turing machines, equivalence of classes of multi-tape and one-tape machines, cost of one-tape 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. Push-down automata, configuration, computation, determninizm, acceptation with accepting states and with empty stack and empty input, push-down automata as Turing machines.
  • 5 XII 2014. Deterministic, nondeterministic and with e-moves 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 e-transitions finite automata. Equivalence of classes regular expressions and finite automata.
  • 19 XII 2014. Proof of pumping lemma for regular languages, Myhill-Nerode theorem with proof. Closeness of classes of regular, context-free and context-sensitive 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, 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

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.