- Teoria automatów i języków formalnych
Ćwiczenia i laboratoria odbywają się co dwa tygodnie naprzemiennie.
Terminy zajęć:
| Lp. | Ćwiczenia | Laboratorium | Temat | Przykładowe zadania |
|---|---|---|---|---|
| 1. | 02.10.2018 | 09.10.2018 | - Relacja, relacja dwuargumentowa, relacja binarna, własności relacji binarnej - Relacja równoważności, klasy równoważności (abstrakcji) - Domknięcie relacji nad zbiorem własności - Alfabet, słowo nad alfabetem, zbiór wszystkich słów nad alfabetem, język - Relacja indukowana przez język, relacja prawostronnie niezmiennicza |
- zad 1 - zad 2 - zad_3 |
| 2. | 16.10.2018 | 23.10.2018 | - Wyrażenia regularne, języki regularne - Kontrapozycja lematu o pompowaniu - Lemat Mynhilla-Nerode'a |
- zad 1 - zad 2 |
| 3. | 30.10.2018 | 06.11.2018 | - Upraszczanie gramatyk bezkontekstowych - Postać normalna Chomsky'ego - Postać normalna Greibach |
- zad 1 - przykład |
| 4. | 13.11.2018 | 20.11.2018 | - Konstruowanie gramatyk bezkontekstowych - Sprawdzanie przynależności słowa do języka bezkontekstowego, algorytm CYK - Kontrapozycja lematu o pompowaniu dla języków bezkontekstowych |
- zad 1 - zad 2 |
| 5. | 27.11.2018 | 04.12.2018 | - Maszyny Turinga |
- zad 1 |
| 6. | 11.12.2018 | 18.12.2018 | - Automaty ze stosem | - zad 1 |
| 7. | 09.01.2019 | 15.01.2019 | - Automaty skończone - Konwersja różnych wersji automatów skończonych |
- zad 1 (12.2.4, 12.2.5) |
| 8. | 22.01.2019 | - Zadania poprawkowe |