3813100539

automatu skończonego. Na początku wprowadzono definicję skończenie stanowej maszyny i wyjaśniono, w jaki sposób wykonuje ona obliczenia na skończonych słowach. Następnie pojęcie skończenie stanowej maszyny rozszerzono do pojęcia automatu skończonego. Sformułowano definicje słowa akceptowanego oraz języka rozpoznawanego przez automat skończony, po czym zaprezentowano przykłady automatów skończonych i języków przez nie rozpoznawanych, opracowane przez autorkę samodzielnie. W ostatnim podrozdziale wykazano, że dla dowolnego niedeterministycznego automatu skończonego istnieje deterministyczny automat skończony, który rozpoznaje ten sam język (Twierdzenie 1.18). Twierdzenie odwrotne jest oczywiste.

Rozdział drugi, poświęcony automatom Biichi’ego, stanowi wstęp do rozważań nad skończonymi maszynami wykonującymi nieskończone obliczenia. W początkowym paragrafie wyjaśniono, w jaki sposób skończenie stanowa maszyna przeprowadza obliczenia na nieskończonych słowach. Następnie wprowadzono pojęcia deterministycznego i niedeterministycznego automatu Biichi’ego oraz słowa akceptowanego i języka rozpoznawanego przez ten automat. Głównym rezultatem tego rozdziału jest Twierdzenie 2.21 mówiące o tym, że istnieją języki, które są akceptowane przez niedeterministyczne automaty Buchiego, ale których nie zaakceptuje żaden deterministyczny automat Buchi’ego. Tak więc jest istotna różnica miedzy tymi dwoma pojęciami.

W rozdziale trzecim przedstawiono propozycje Mullera, Rabina i Streeta alternatywnych definicji maszyny skończenie stanowej wykonującej nieskończone obliczenia. Podobnie jak automaty skończone i automaty Biichi’ego, każdy z nich występuje w wersjach: deterministycznej i niedeterministycznej. Okazuje się, że w przeciwieństwie do automatów Biichi’ego dla każdego z tych alternatywnych typów obie wersje są równoważne [...]. W rozdziale trzecim przedstawiono też pewne przekształcenia między różnymi typami automatów, wykorzystywane później w rozdziale czwartym w dowodzie głównego twierdzenia.

Główny rezultat rozdziału czwartego, Twierdzenie 4.3, głosi, że dla dowolnych dwóch z podanych w tej pracy definicji automatów niedeterministycznych realizujących nieskończone obliczenia, automat pierwszego typu można przekształcić w automat drugiego typu rozpoznający ten sam język. Tak więc niedeterministyczne automaty Biichi’ego, Mullera, Rabina i Streeta są wzajemnie równoważne pod względem mocy obliczeniowej.

Przygotowując pracę magisterską korzystano przede wszystkim z [3, 1] pomocniczo używając pozostałych pozycji z literatury. Układ pracy oraz komentarze zostały opracowane przez autorkę w dyskusji z promotorem. Dowody twierdzeń zaczerpnięte z literatury znacząco dopracowano. Wymagało to przełożenia poglądowych opisów działania danych maszyn na twarde, logiczne rozumowanie matematyczne, oparte na znanych definicjach.

3