- Teoria automatów i języków formalnych
Regulamin przedmiotu
Literatura:- Homenda W., Elementy lingwistyki matematycznej i teorii automatów, OWPW 2005 - pdf
- Homenda W., Formal languages and automata, Lecture
notes, Warszawa, 2010 - pdf
- Hopcroft
J. E., Motwani R., Ullman J. D., Wprowadzenie do teorii automatów, języków i
obliczeń, Wydawnictwo Naukowe PWN, 2005
- Hopcroft
J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages,
and Computation, Pearson Education Limited, 2013
- Homenda
W., Pedrycz W., Automata Theory and Formal Languages, de Gruyter, 2022
- Homenda W., Elementy lingwistyki matematycznej i teorii automatów, OWPW 2005 - pdf
- Homenda W., Formal languages and automata, Lecture notes, Warszawa, 2010 - pdf
- Hopcroft J. E., Motwani R., Ullman J. D., Wprowadzenie do teorii automatów, języków i obliczeń, Wydawnictwo Naukowe PWN, 2005
- Hopcroft J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Pearson Education Limited, 2013
- Homenda W., Pedrycz W., Automata Theory and Formal Languages, de Gruyter, 2022
Realizacja zajęć:
| Lp. | Ćwiczenia pon/wt | Tematy - grupa poniedziałkowa (1 h) | Tematy - grupy wtorkowe (2 h) | Materiały |
|---|---|---|---|---|
| 1. | 03.10.2022 04.10.2022 | 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 | - 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 - Alfabet, słowo, język | - Zadania: 1.1, 1.2 |
| 2. | 10.10.2022 11.10.2022 | - Relacja prawostronnie niezmiennicza - Relacja indukowana przez język - wyznaczanie klas abstrakcji tych relacji | - Relacja prawostronnie niezmiennicza - Relacja indukowana przez język - wyznaczanie klas abstrakcji tych relacji | - Zadania: 2.1, 2.2 |
| 3. | 17.10.2022 18.10.2022 | - Konstrukcja wyrażeń regularnych - Badanie regularności języków za pomocą lematu Myhill-Nerode, oraz lematu o pompowaniu | - Konstrukcja wyrażeń regularnych - Konstrukcja gramatyk regularnych lewostronnych i prawostronnych - Badanie regularności języków za pomocą lematu Myhill-Nerode, oraz lematu o pompowaniu | - Zadania: 3.1, 3.2 |
| 4. | 24.10.2022 25.10.2022 | - Konstrukcja gramatyk bezkontekstowych | - Konstrukcja gramatyk bezkontekstowych - Upraszczanie gramatyk bezkontekstowych - usuwanie symboli bezużytecznych, zmiana statusu symboli wycieralnych, usuwanie produkcji jednostkowych | - Zadania: 4.1 |
| 5. | 07.11.2022 08.11.2022 | - Upraszczanie gramatyk bezkontekstowych - usuwanie symboli bezużytecznych, zmiana statusu symboli wycieralnych, usuwanie produkcji jednostkowych | - Sprowadzanie gramatyk bezkontekstowych do postaci normalnych Chomskiego i Greibach | - Zadania: 5.1 |
| 6. | 14.11.2022 15.11.2022 | - Sprowadzanie gramatyk bezkontekstowych do postaci normalnych Chomskiego i Greibach | - Wykorzystanie lematu o pompowaniu dla języków bezkontekstowych - Algorytm CYK | - Zadania: 6.1 |
| 7. | 21.11.2022 22.11.2022 | - Wykorzystanie lematu o pompowaniu dla języków bezkontekstowych | - Kolokwium 1 | |
| 8. | 28.11.2022 29.11.2022 | - Algorytm CYK | - Konstrukcja gramatyk kontekstowych i nieograniczonych | - Zadania: 8.1 |
| 9. | 05.12.2022 06.12.2022 | - Maszyny Turinga - model podstawowy | - Maszyny Turinga - model podstawowy, z wartownikiem i z taśmą obustronnie nieograniczoną | - Zadania: 9.1 |
| 10. | 12.12.2022 13.12.2022 | - Maszyny Turinga wielościeżkowe i wielotaśmowe | - Maszyny Turinga wielościeżkowe i wielotaśmowe | - Zadania: 10.1 |
| 11. | 19.12.2022 20.12.2022 | - Niedeterministyczne maszyny Turinga | - Niedeterministyczne maszyny Turinga, automat liniowo ograniczony | - Zadania: 11.1 - Zadania: 11.2 |
| 12. | 02.01.2023 03.01.2023 | - Automaty ze stosem | - Automaty ze stosem | - Zadania: 12.1 |
| 13. | 09.01.2023 10.01.2023 | - 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 | - 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 | - Zadania: 13.1 |
| 14. | 16.01.2023 17.01.2023 | - Konwersja niedeterministycznych automatów skończonych z epsilon ruchami na automaty deterministyczne | - Konwersja niedeterministycznych automatów skończonych z epsilon ruchami na automaty deterministyczne | Zadania w 13.1 |
| 15. | 23.01.2022 24.01.2023 | - Kolokwium | - Kolokwium 2 |
Prowadzący wykład:
Ćwiczenia z TAiJF prowadzą: