614372762

Uniwersytet Zielonogórski Instytut Sterowania i Systemów Informatycznych

Teoretyczne Podstawy Informatyki

Lista 4 - Deterministyczne i niedeterministyczne automaty 1 Wprowadzenie

Automat skończony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach. System taki może się znajdować w jednym ze skończonej liczby stanów (dopuszczalne są także systemu gdzie automat może się znajdować w wielu stanach na raz). Stan systemu stanowi podsumowanie informacji dotyczących poprzednich wejść. Informacja ta jest niezbędna aby do określenia zachowania systemu przy następnych wejściach. Istnieje wiele przykładów zastosowań automatów. Prostym przykładem jest mechanizm windy. Mechanizm ten nie pamięta wszystkich poprzednich żądań. Pamiętane jest tylko bieżące piętro, kierunek ruchu (w górę lub w dół) oraz zbiór żądań do obsłużenia.

Innymi przykładami stanowią powszechnie używane programy, takie jak edytory tekstów i analizatory leksykalne spotykane w większości kompilatorów. Są one bardzo często projektowane jako systemy skończenie stanowe. Analizator leksykalny przegląda symbole programu komputerowego w celu zlokalizowania łańcuchów symboli odpowiadających identyfikatorom, stałym numerycznym, słowom kluczowym oraz innymi jednostkom leksykalnym. W trakcie tego procesu analizator leksykalny pamięta tylko skończoną ilość informacji, takich jak np.: jak długi przedrostek słowa kluczowego był widziany chwili startu. Teoria automatów skończonych ma bardzo duży udział w projektowaniu efektywnych analizatorów łańcuchów.

Przykład analizy, gdzie znajduje zastosowanie opis przy pomocy automatu skończonego może zostać zaprezentowany na przykładzie następującego problemu: na brzegu rzeki stoi człowiek z wilkiem, kozą i sałatą. Zadaniem jest przedostanie się na drugą stronę rzeki. Utrudnieniem są pewne warunki, człowiek może przepłynąć rzekę tylko z jednym pasażerem, czyli albo z wilkiem, albo z kozą bądź z sałatą. Jeśli jednak zostawi on wilka i kozę bez nadzoru na którymkolwiek brzegu, to wilk pożre kozą. Jeśli koza i sałata zostaną bez opieki, to koza pożre sałatę.

Rysunek 1: Diagram przejść do problemu człowieka, wilka kozy oraz sałaty

Właściwe rozwiązanie zostanie odnalezione, gdy zauważymy, że istotną informacją jest to, jakie obiekty znajdują się na każdym z brzegów po dowolnej stronie rzeki. Można wskazać, że istnieje szesnaście podzbiorów złożonego z człowieka (C), wilka (W), kozy (K) oraz sałaty (S). Zakładamy, że stan odpowiada podzbiorowi, który opisuje co znajdującemu się na lewym i prawym brzegu. Do zwiększenia czytelności będzie stosować kreskę do rozdzielenia obiektów znajdujących się na lewym oraz prawym brzegu. Przykład stanu WS — CK oznacza, że wilka i sałata znajdują się na lewym a na prawym brzegu jest człowiek i koza.

Wejścia systemu to działania podejmowane przez człowieka. Człowiek może się przeprawiać sam, z wilkiem, z kozą i naturalnie z sałatą. Stanem początkowym jest CWKS — # a końcowym # — CWKS (gdzie symbol # oznacza iż dany brzeg jest pusty). Diagram przejść który pokazuje sposób rozwiązania przedstawia rysunek 1. Litery na lukami oznaczają pasażera który został przewieziony przez człowieka.