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 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. Myhill-Nerode lemma, pumping lemma, examples. Grammars, definition, direct derivation, derivation, language generated. Left hand side and right hand side derivations.
  • 19 X 2018. Context-free grammars, useless symbols, nullable symbols, unit productions.
  • 26 X 2018. Normal forms of context-free grammars: Chmosky and Greibach, transformation to normal forms. Pumping lemma for context-free languages.
  • 9 XI 2018. Pumping lemma for context-free languages, proof, example. CYK algorithm.
  • 16 XI 2018. 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.
  • 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 multi-track 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. Push-down automata, summary. Finite automata deterministic and nondeterministic, configuration, move, computation, acceptation of input, language accepted.
  • 21 XII 2018. Finite automata with e-transitions, configuration, move, computation. Equivalence of classes of finite automata deterministic, nondeterministic and with e-transitions.
  • 4 I 2019. Equivalence of classes of finite automata and regular expressions, proof. Pumping lemma for regular languages, proof. Myhill-Nerode Theorem, proof.
  • 11 I 2019. Equivalence of classes of: context free grammars and push-down 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 context-free and context-sensitive 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, 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 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.