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
Wyszukiwarka
Podobne podstrony:
1.1.1. Pojęcie skończenie stanowej maszyny Niech E będzie alfabetem. Definicja 1.1. Niedeterministyc
Wymagania wstępne: podstawy algebry i logiki Automaty skończenie stanowe. Automaty minimalne. Minima
Właściwe wykorzystanie symboli PCS wymaga przestrzegania kilku reguł i zasad: ❖na początku wprowadza
Poznaj C++ w$ godziny0035 Program w C++ 19Funkcje ■ain() jest funkcją specjalną. Jest automatycznie
Jak zawsze na początku wprowadzenie w istotę zagadnienia!
Definicja 1.3 Przez język automatu skończonego A rozumiemy zbiór L(A) wszystkich słów akceptowanych
Zadanie 32. a. Jaką minimalną liczbę stanów musi mieć deterministyczny automat skończony rozpoznając
1.2.1. Definicja automatu skończonego Niech E będzie alfabetem. Definicja 1.10. Niedeterministycznym
<4>Informatyka + Streszczenie Wyktad. Na początku zostaną wprowadzone podstawowe definicje
1.1 Definicja deterministycznego automatu skończonego Deterministyczny automat
Rozdział 1Podstawowe pojęcia i oznaczenia1.1. Automaty skończone na słowach Punktem wyjścia do rozwa
utomatówP TA m odstawy m eoriiW ■1. NAS, DAS, definicje, różnice Automat skończony jest modelem
więcej podobnych podstron