Spis zagadnień z egzaminu podawany w środę przez Gniewka: +1. Wyznaczyć język generowany przez gramatykę +2. Przekształcić gramatykę do gramatyki bez reguł bezużytecznych i zerowych +3. Przekształcić gramatykę do gramatyki monotonicznej +4. Przekształcić gramatykę do postaci Chomskiego +5. Przekształcić gramatykę Greibach +6. Wyznaczyć język bezkontekstowy L będący konkatencją, sumą lub domknięciem Kleene'ego danych języków L1 i L2 +7. Wyznaczyć gramatykę dla danego języka skończonego +8. Podać wyrażenia regularne opisujące dany język skończony. +9. Podać wzory (metoda V) opisujące wybrane elementy tablicy algorytmu C-Y-K(Na egzaminie obowiązuje jedynie metoda V) +10. Sprawdzić CYK czy dane słowo należy do języka =/-11. Dane wyrażenie regularne przekształcić do danej postaci wykorzystując związki w algebrze wyrażeń regularnych(Będą podane wzory potrzebne + kilka niepotrzebnych, nie ma potrzeby uczenia się na pamięć) -12. Przekształcić gramatykę regularną by symbol początkowy nie występował po prawej stronie reguł produkcji +13. Przekształcić do postaci deterministycznej +14. Przekształcić do postaci zupełnej 15. Zapisać język L przy użyciu wyrażeń regularnych. Narysować wykres gramatyki regularnej opisujący ten język. Wyznaczyć gramatykę regularną opisującą dany język L. 16. Ocenić czy dany język jest regularny, bezkontekstowy, kontekstowy, rekurencyjnie policzalny. +17. Jak liczny jest dany język L (podać liczbę elementów języka) +18. Napisać układ równań dla danego układu Moora i rozwiązać go ze względu na dane RXY +19. Napisać układ równań dla danego układu Meolyłego i rozwiązać go ze względu na dane RXY +20. Narysować graf automatu Meolyłego +21. Wyznaczyć dla automatu Meolyłego równoważny automat Moora +22. Wyznaczyć dla automatu Moora równoważny automat Meolyłego +/-23. Pokazać czy dane wyrażenie jest akceptowane przez automat ze stosem (możliwe zakleszczenie) 24. Pokazać czy wyrażenie jest akceptowane przez maszynę Turinga