3813100542

Rozdział 1

Automaty skończone

Głównym celem tego rozdziału jest zapoznanie czytelnika z pojęciem skończenie stanowej maszyny oraz wyjaśnienie idei determinizmu i niedeterminizmu. Automat skończony, jako maszyna o skończonej liczbie stanów, wykonująca obliczenia na skończonych słowach, jest najprostszym modelem obliczeń. Teoria automatów skończonych stanowi punkt wyjścia do rozważań teorii automatów Buchi’ego.

W ostatnim paragrafie tego rozdziału pokażemy, że klasy niedeterministycz-nych i deterministycznych automatów skończonych są sobie równoważne, tzn. że dla dowolnego deterministycznego automatu skończonego istnieje niedetermini-styczny automat skończony, który rozpoznaje ten sam język i na odwrót. Ponadto przedstawimy proces determinizacji niedeterministycznego automatu skończonego. Jak zobaczymy w rozdziale drugim, analogiczny proces w przypadku automatów Buchi’ego musi skończyć się porażką.

W niniejszym rozdziale niektóre z podanych pojęć (Definicje 1.1, 1.2) zostały sformułowane na potrzeby tej pracy samodzielnie przez autorkę, w oparciu o literaturę. Pojęcie obliczenia maszyny skończenie stanowej na skończonym słowie (Definicja 1.5) nie występuje w literaturze lub pojawia się pod inną nazwą ([4]). Inne (1.10,1.11,1.12,1.13) można znaleźć w literaturze [3, 6, 2] , a definicje tu podane są im równoważne. W rozdziałach późniejszych, formułując definicje pojęć wzorowanych na literaturze, wykorzystano te definicje z obecnego rozdziału.

1.1. Skończenie stanowe maszyny wykonujące obliczenia na skończonych słowach

W tym podrozdziale przedstawimy pojęcie skończenie stanowej maszyny oraz zilustrujemy je na kilku przykładach. Następnie wyjaśnimy, jak skończenie stanowe maszyny wykonują obliczenia na skończonych słowach.

6