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: Turing machine that computes ceiling of logarithm base 2 of n, n is in unary pos. system, two-tape Turing machine (a) machine that accepts palindromes, (b) machine that accepts words of shape ww (double word w), (c) machine that adds two binary numbers
17.12.2019: non-deterministic Turing machines. Exercises: a machine that accepts palindromes, the alphabet is made of two symbols, (non-deterministic, two tapes), a machine that accepts words of the form ww where w is a non-empty word, the alphabet is made of two symbols, (non-deterministic, one tape with guard)
07.01.2020: push-down automata. Exercises: automaton that accepts palindromes of even length including empty word (the alphabet is made of symbol a and symbol b); automaton that accepts palindromes in the form wcw^R, where w is a word made of letters a and b (can be empty) and w^R is this word in a reverse order, c is a letter; automaton that accepts any palindrome including empty word; automaton that accepts words which after splitting in any place break into two palindromes, breaking can be in any place including a break into empty word and the starting word. Automaton (regular, deterministic) that accepts words in which in a prefix of any length the difference between the number of occurrences of 0s and 1s is not greater than 2, the prefix can be of any length including the full word length.
14.01.2020: transitioning from regular expressions to automata and from automata to regular expressions
21.01.2020: transitioning from automaton with epsilon moves to a nondeterministic automaton and then to deterministic automaton; Cartesian product of two automata (accepting even numbers and empty word, accepting numbers divisible by 3)
28.01.2020: test

### 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: WC: 1/2, FSz: 1/2, TN:1/2
03.12.2019: -
10.12.2019: BŻ 1/2, WC 1/2, TN 1/2, GJ 1/2
17.12.2019: TN, JB, PO, BŻ, FS, WC, MM, JZ, GJ, SaAs (each 1/2pt)
07.01.2020:JB 1/2+1/2, TN 1/2, LJ 1/2
14.01.2020:  JB: 1/2, FZ: 1/2
21.01.2020: JB: 1/2, FZ: 1/2
28.01.2020:

### Results test I

JB 12, WC 12, WD 16, YI 2, GJ 8, AK 2, JL 6, JSL 6, MM 6, TN 14, PO 12, KR 10, AsSa 14, IS 2, JSS 14, KSk 12, AdSt 6, KSt 8, FS 16, PW 3, MZ 10, FZ 10, JZ 4, RZ 7,BŻ 2

### Results test II

JB 4, WC 8, WD 6, GJ 6, JL 6, TN 9, PO 5, IS 4, JSS 8, KSk 6, FS 8, PW 10, FZ 10, JZ 7, BŻ 6

### Test II, topic particularly useful while preparing for the test

• Turing machines
• push-down automata
• transitioning from regular expression to automaton
• transitioning from automaton with epsilon moves to a nondeterministic automaton and then to deterministic automaton

### Students exempt from the practical part of the exam (including dr Luckner's group)

first three letters were used here: Mikhoś, Szymaj, Filszy, Eliozd, Tomnaw, Wojdrę, Dzihar, JulSem, Frałuk, Wojcio, Filzaw, Rozkor, Vlasor, Pawgra, Damros, Jakbła, Korskó, Pawolę, Łukkaw, Rafbog.

### Activity points (sum, scaled appropriately)

FS 3, TN 5.67, FZ 6, WC 3.67, JB 11, PO 1, AsSa 1, MaMr 1, GJ 5, JZ 1, BŻ 3, JL 1

FS, TN, FZ, JB

### EXAM RESULTS, 4th Feb 2020

part with exercises: AA2, MA2, MED2, HH2, YI2, IS2, JZ2, MM3, MR3, BŻ3, KR3, AdSt3.5, BTA3.5, PW4.5, JL4.5
theory: MED2, MR2, KR2, WD2, DR2, AsSa3, BTA3.5, EO4, PW4, FŁ5