- Automata Theory and Formal Languages
Regulations
Homenda Władysław - Formal languages and automata.pdf
Classes realization:
| No | Meeting | Topic | Remarks |
|---|---|---|---|
| 1. | - Relations | M. Luckner | |
| 2. | - Relation induced by language | M. Luckner | |
| 3. | 18.10.2021 ✔ | - Construction of regular expressions - Analysis of the regularity of languages using the Myhill-Nerode Lemma | - Tasks |
| 4. | 25.10.2021 ✔ | - Analysis of the regularity of languages using the Myhill-Nerode Lemma - Analysis of the regularity of languages using the Pumping Lemma | - Tasks |
| 5. | 08.11.2021 ✔ | - Construction of left-linear and right-linear regular grammars - Construction of context-free grammars | - Tasks |
| 6. | 15.11.2021 ✔ | - Simplification of context-free grammars | - Tasks |
| 7. | 22.11.2021 ✔ | - Using the pumping lemma for context-free languages - CYK algorithm | - PL tasks - CYK tasks |
| 8. | 29.11.2021 ✔ | - Test 1 | Test |
| 9. | 06.12.2021 ✔ | - Context-sensitive and unrestricted grammars | - Tasks |
| 10. | 13.12.2021 ✔ | - Turing machines - basic model, with a guard and with two-way infinite tape | |
| 11. | 20.12.2021 ✔ | - Multi-track and multi-tape Turing machines - Sketch of proof of equivalence of multi-tape and multi-track TM | |
| 12. | 03.01.2022 ✔ | - Deterministic Finite Automata | |
| 13. | 17.01.2022 ✔ | - Automaty skończone - Konstrukcja minimalnych automatów skończonych w oparciu o twierdzenie Myhill-Nerode - Konstrukcja minimalnych automatów skończonych w oparciu o dzielenie języków - Nondeterministic finite automata - Nondeterministic finite automata with epsilon moves - Conversion of nondeterministic finite automata with epsilon moves into deterministic automata | |
| 14. | 24.01.2022 ✔ | - Construction of minimal finite automata based on the Myhill-Nerode theorem - Construction of minimal finite automata based on the quotients of languages | |
| 15. | 26.01.2022 ✔ | - Construction of minimal finite automata based on the quotients of languages (continued) - Revision | Wednesday 6.00 pm |
| 16. | 31.01.2022 ✔ | - Test 2 | Test + open sample test (polish) sample test (english) |