Tematy na egzamin ustny.

Na ocenę 3 trzeba poprawnie odpowiedzieć na dwa spośrod tematów 1-14 z poniższej listy (wybrane przez egzaminatora). Na ocenę > 3 trzeba poprawnie odpowiedzieć na dwa-trzy tematy z całej poniższej listy. Na ogół odpowiedź będzie wymagała sformułowania i udowodnienia jakiegoś twierdzenia. Podzczas egzaminu mogą też paść dodatkowe pytania blisko związane z poniższymi tematami.

1. Udowodnić twierdzenie o determinizacji automatów skończonych. Podać przykład wykładniczego wzrostu rozmiaru automatu podczas determinizacji.
2. Udowodnić twierdzenie o równoważności wyrażeń regularnych i automatów skończonych.
3. Udowodnić lemat o pompowaniu dla języków regularnych.
4. Udowodnić, że klasa językow regularnych jest zamknięta na: sumy, przecięcia, dopełnienia, konkatenacje, ilorazy lewo- i prawostronne.
5. Podać algorytmy dla następujących problemów dla języków regularnych: minimalizacja, niepustość, równoważność.
6. Podać definicję gramatyki bezkontekstowej i generowanego przez nią języka.
7. Pokazać algorytmy dla następujących problemów dla gramatyk bezkontekstowych: niepustość języka, nieskończoność języka.
8. Udowodnić lemat o pompowaniu dla języków bezkontekstowych.
9. Zdefiniować automat ze stosem. Udowodnić równoważność akceptacji przez pusty stos i akceptacji przez stany.
10. Udowodniść równoważność gramatyk bezkontekstowych i automatów ze stosem.
11. Podać algorytm wielomianowy rozpoznawania języków bezkontekstowych.
12. Udowodnić, że klasa języków bezkontekstowych jest zamknięta na sumy, przecięcia z językami regularnymi, konkatenacje; a nie jest zamknięta na przecięcia i dopełnienia.
13. Zdefiniować pojęcie rozstrzygalności i częściowej roztrzygalności.
14. Podać przykład dwóch języków nierozstrzygalnych i redukcji pomiędzy nimi.

15. Udowodnić, że deterministyczne języki bezkontekstowe są jednoznaczne.
16. Udowodnić twierdzenie Parikha.
17. Udowodnić nierozstrzygalność wybranego problemu decyzyjnego dla gramatyk bezkontekstowych (np. uniwersalność lub niepustość przecięcia).
18. Dowód nierozstrzygalności problemu odpowiedniości Posta.
19. Udowodnić równoważność maszyn Turinga i maszyn licznikowych.
20. Udowodnić równoważność maszyn Turinga i gramatyk typu 0.
21. Udowodnić NP-zupełność problemu SAT.
22. Zdefiniować klasę NP i pojęcie redukcji wielomianowej.
23. Zdefiniować klasę PSPACE i podać problem dla niej zupełny.