- Teoria automatów i języków formalnych
Ćwiczenia i laboratoria odbywają się co dwa tygodnie naprzemiennie.
Terminy laboratoriów:
| Lp. | Ćwiczenia | Laboratorium | Temat | Przykładowe zadania |
|---|---|---|---|---|
| 1. | 04.10.2016 | 11.10.2016 | - 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. | 18.10.2016 | 25.10.2016 | - Wyrażenia regularne, języki regularne. - Kontrapozycja lematu o pompowaniu. - Lemat Mynhilla-Nerode'a |
- zad 1 - zad 2 |
| 3. | 08.11.2016 | 15.11.2016 | - Upraszczanie gramatyk bezkontekstowych. - Postać normalna Chomsky'ego. - Postać normalna Graibach |
- zad 1 - przykład |
| 4. | 22.11.2016 | 29.11.2016 | - 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. | 06.12.2016 | 13.12.2016 | - Maszyny Turinga - Automaty ze stosem |
- zad 1 - zad 2 |
| 6. | 20.12.2016 | 03.01.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. | 10.01.2017 | 17.01.2017 | - Niedeterministyczne automaty skończone - Konwersja różnych wersji automatów skończonych |
|
| 8. | 24.01.2017 | - Zadania poprawkowe |