- Teoria automatów i języków formalnych
Regulamin przedmiotu
Realizacja zajęć:
| Lp. | Ćwiczenia | Temat | Uwagi |
|---|---|---|---|
| 1. | 05.10.2021 ✔ | - Relacja, relacja dwuargumentowa, relacja binarna, własności relacji binarnej - Relacja równoważności, klasy równoważności (abstrakcji), liczność klas abstrakcji - Domknięcie relacji nad zbiorem własności | - zad 1 - zad 2 |
| 2. | 12.10.2021 ✔ | - Relacje indukowane przez języki - wyznaczanie klas abstrakcji tych relacji | - zad 1 - zad 2 |
| 3. | 26.10.2021 ✔ | - Konstrukcja wyrażeń regularnych - Badanie regularności języków za pomocą lematu Myhill-Nerode, oraz lematu o pompowaniu | - zad 1 - zad 2 |
| 4. | 02.11.2021 ✔ | - Konstrukcja gramatyk regularnych lewostronnych i prawostronnych - Konstrukcja gramatyk bezkontekstowych | - zad |
| 5. | 09.11.2021 ✔ | - Usuwanie symboli bezużytecznych, zmiana statusu symboli wycieralnych, usuwanie produkcji jednostkowych - Sprowadzanie gramatyk bezkontekstowych do postaci normalnych Chomskiego i Greibach | |
| 6. | 16.11.2021 ✔ | - Wykorzystanie lematu o pompowaniu dla języków bezkontekstowych - Algorytm CYK | |
| 7. | 23.11.2021 ✔ | - Kolokwium 1 | Test |
| 8. | 30.11.2021 ✔ | - Konstrukcja gramatyk kontekstowych i nieograniczonych | - zad |
| 9. | 07.12.2021 ✔ | - Maszyny Turinga - model podstawowy | - zad |
| 10. | 14.12.2021 ✔ | - Maszyny Turinga z wartownikiem i z taśmą obustronnie nieograniczoną, MT wielościeżkowe | |
| 11. | 04.01.2022 | - Maszyny Turinga wielotaśmowe - Niedeterministyczne maszyny Turinga | |
| 12. | 11.01.2022 ✔ | - Automaty ze stosem | |
| 13. | 18.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 | |
| 14. | 25.01.2022 ✔ | - Konwersja niedeterministycznych automatów skończonych z epsilon ruchami na automaty deterministyczne | |
| 15. | 01.02.2022 ✔ | - Kolokwium 2 | Test + otwarte przykładowy test |
Prowadzący wykład:
Ćwiczenia z TAiJF prowadzą: