- Teoria automatów i języków formalnych
Regulamin przedmiotu
Realizacja zajęć:
| Lp. | Ćwiczenia | Temat | Uwagi |
|---|---|---|---|
| 1. | 05.10.2020 | - 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.2020 | - Indukcja matematyczna - Definicja drzewa - Relacje indukowane przez języki - wyznaczanie klas abstrakcji tych relacji |
- zad 1 - zad 2 |
| 3. | 20.10.2020 | - Konstrukcja wyrażeń regularnych - Badanie regularności języków za pomocą lematu Myhill-Nerode, oraz lematu o pompowaniu |
- zad 1 - zad 2 |
| 4. | 27.10.2020 | - Konstrukcja gramatyk regularnych lewostronnych i prawostronnych - Konstrukcja gramatyk bezkontekstowych |
- zad |
| 5. | 03.11.2020 | - Usuwanie symboli bezużytecznych, zmiana statusu symboli wycieralnych, usuwanie produkcji jednostkowych - Sprowadzanie gramatyk bezkontekstowych do postaci normalnych Chomskiego i Greibach |
|
| 6. | 10.11.2020 | - Wykorzystanie lematu o pompowaniu dla języków bezkontekstowych - Algorytm CYK |
|
| 7. | 20.11.2020 | - Kolokwium 1 (piątek godz. 16.00) |
Test |
| 8. | 24.11.2020 | - Konstrukcja gramatyk kontekstowych i nieograniczonych |
- zad |
| 9. | 01.12.2020 | - Maszyny Turinga - model podstawowy, z wartownikiem i z taśmą obustronnie nieograniczoną |
- zad |
| 10. | 08.12.2020 | - Maszyny Turinga wielościeżkowe i wielotaśmowe. Szkic dowodu równoważności maszyny wielotaśmowej i wielościeżkowej. Koszt symulacji maszyny wielotaśmowej za pomocą maszyny jednotaśmowej. | |
| 11. | 15.12.2020 | - Maszyny Turinga wielotaśmowe - Maszyny Turinga liniowo ograniczone - Niedeterministyczne maszyny Turinga |
|
| 12. | 22.12.2020 | - Automaty ze stosem |
|
| 13. | 12.01.2021 | - 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. | - Konwersja niedeterministycznych automatów skończonych z epsilon ruchami na automaty deterministyczne |
||
| 15. | - Kolokwium 2 |
Test + otwarte |
Prowadzący wykład:
Ćwiczenia z TAiJF prowadzą: