Automata Theory and Formal Languages

Course coordinator and lecturer:
prof. dr hab. inż. Władysław Homenda

Tutorials are also conduced by:
dr inż. Marcin Luckner

### Schedule:

08.10.2019: multi-argument relations, two-argument relations, binary relations. Equivalence classes. Defining equivalence classes. Counting the number of equivalence classes for particular problems. Examples of equivalence classes made of finite and infinite number of elements. Examples: in a relation we have words of the same length, in a relation we have words containing the same symbols (letters), in a relation we have words containing the same symbols and the count of these symbols is equal, in a relation we have binary words in which the number of occurrences of 0s and 1s is the same, in a relation we have binary words in which when we divide the difference of the number of occurrences of 0s and 1s by three we get the same number. Mathematical induction.
15.10.2019: Definition of a tree. Lemma about the number of leaves in a k-tree. Relation induced by a language. Exercises: language made of binary words that contain exactly one sequence of triple 1s, language made of binary words in which the difference between the number of occurrences of 0s and 1s is divisible by 3.
22.10.2019: Myhill-Nerode theorem, application to the following tasks: language made of binary words that end with triple 1s, language made of words that contain each letter from a given alphabet. Pumping lemma for regular languages, pumping lemma contrapositive. Verification if a given language is not regular using the pumping lemma contrapositive. Example exercises: (a) language made of words a^ib^i, i>1. (b) language made of words where subsequent sequences of 0s and 1s are of an increasing length. (c) language made of words where subsequent sequences are of a decreasing length (d) language made of binary words where the number of occurrences of 0s is smaller then the number of occurrences of 1s.
29.10.2019: regular expressions: language made of binary numbers without insignificant 0s, language made of binary words where there exists at least one sequence of triple 1s and at least one sequence of triple 0s, language made of binary words that start with 0 and have optionally many sequences made of one 0 and at least one 1, the words at the end have either end a 1 or a 0, homework: language made of binary words where there exists exactly one sequence of triple 1s and exactly one sequence of triple 0s. Right and left-linear grammars. Examples: language made of binary numbers without insignificant 0s, language made of binary words where there exists at least one sequence of triple 1s and at least one sequence of triple 0s.
05.11.2019: context-free grammars: generating language od binary words where the number of 0s is equal to the number of 1s without empty word, generating language od binary words where there are twice as many 0s as 1s, without empty word, language over the alphabet {a,b,c,d} made of words of the following form a^(n+m)b^kc^(k+l)d^n, k,l,n,m>0, useless symbols/productions: non-generative, non-reachable with example, nullable symbols: algorithm for removal
12.11.2019: context-free grammars: Chomsky normal form, Greibach normal form, pumping lemma for context-free languages, example: language made of words such that a^kb^lc^m, k>l>m
19.11.2019: test! we moved the test to December, CYK algorithm for checking if a given word can be derived from a given grammar, unrestricted grammars, context-sensitive grammars, example language where words are made of a's and b's and # of a's = n and the # of b's = 2^n, n>=1
26.11.2019: Turing machines: Turing machine that multiplies a given number in the unary pos. system by 3, Turing machine that accepts words in the form a^nc^nd^n, n is a natural number >=0, Turing machine that accepts binary words where the number of 0s is the same as the number of 1s, homework: Turing machine that computes ceiling of logarithm base2 of n, n is in unary pos. system
03.12.2019: test!, sample test
10.12.2019:
17.12.2019:
07.01.2020:
14.01.2020:
21.01.2020:
28.01.2020:

### Announcements:

Rules are on the course coordinator webpage
Example exercises are on the webpage of dr Janusz Rafałko.
You may see a collection of tasks for practice prepared by dr Marcin Luckner here

### Extra activity points:

08.10.2019: JB: 1/2+1/2, FZ: 1/2+1/2, TN: 1/3
15.10.2019: JB: 1/2
22.10.2019: JB: 1/2, FZ: 1/2, TN: 1/2, BŻ: 1/2
29.10.2019: JB: 1/2, FZ: 1/2, GJ: 1/2
05.11.2019: GJ: 1/2, LM: 1/2
12.11.2019: -
19.11.2019: JB:1/2, GJ: 1/2, FSz: 1/2, WC: 1/3
26.11.2019: TC: 1/2, FSz: 1/2, TN:1/2
03.12.2019:
10.12.2019:
17.12.2019:
07.01.2020:
14.01.2020:
21.01.2020:
28.01.2020: