- 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. | 03.10.2017 | 10.10.2017 | - 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 |
| 2. | 17.10.2017 | 24.10.2017 | - Wyrażenia regularne, języki regularne. - Kontrapozycja lematu o pompowaniu. - Lemat Mynhilla-Nerode'a |
- zad 1 - zad 2 |
| 3. | 31.10.2017 | 07.11.2017 | - Upraszczanie gramatyk bezkontekstowych. - Postać normalna Chomsky'ego. - Postać normalna Graibach |
- zad 1 - przykład |
| 4. | 14.11.2016 | 21.11.2017 | - 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. | 28.11.2017 | 05.12.2017 | - Maszyny Turinga - Automaty ze stosem |
- zad 1 - zad 2 |
| 6. | 12.12.2017 | 19.12.2017 | - Automaty skończone - Minimalne automaty skończone konstruowane w oparciu o twierdzenie Mynhilla-Nerode'a - Minimalne automaty skończone konstruowane w oparciu o iloraz języków |
- zad 1 - przykład |
| 7. | 09.01.2018 | 16.01.2018 | - Niedeterministyczne automaty skończone - Konwersja różnych wersji automatów skończonych |
- zad 1 (12.2.4, 12.2.5) |
| 8. | 23.01.2018 | - Zadania poprawkowe |