W tym rozdziale poznasz pojęcie automatu oraz dowiesz się czym różnią się automaty deterministyczne i niedeterministyczne.
Pojęcie automatu
Automat,to drugi,obok gramatyki,model obliczeń będący przedmiotem badań teorii języków i automatów. Celem jest rozstrzygnięcie w skończonej ilości kroków,czy dowolne słowo należy,czy też nie należy do języka badanego przez automat. Teoria automatów jest efektem badań zapoczątkowanych przez A. Turinga.
Automatem nad alfabetem A nazywamy system A=(S,f),w którym S –jest dowolnym skończonym zbiorem zwanym zbiorem stanów,a f:S x A → S –jest funkcją przejść.
Automat reaguje na określone sygnały,zmieniając swój stan. Jeśli ustalimy,że sygnały będą reprezentowane przez poszczególne litery alfabetu,zdefiniujemy stan początkowy automatu oraz dopuszczalne stany końcowe,to automat może testować dowolne słowo,startując ze stanu początkowego. Słowo zostanie rozpoznane przez automat i uznane za poprawne,jeżeli rezultatem działania będzie założony stan końcowy. W powyższym przypadku mamy z góry ustaloną ilość możliwych stanów,zatem tak działający automat jest automatem skończonym.
Automat skończony składa się ze skończonego zbioru stanów i zbioru przejść pomiędzy stanami.
Przykład
Rysunek przedstawia bardzo prosty automat skończony,który zachowuje się w sposób stabilny gdy na wejściu otrzymuje wartość A,i zmienia swój stan przy napotkaniu B. Zaczyna on pracę od stanu S1 ,i po przeczytaniu każdego symbolu przechodzi do stanu Sj (gdzie:j=1 lub 2)
- stan startowy –S1
- S1 →1 S1
- S1 →0 S2
- S2 →1 S2
- S2 →0 S1
- Co jest główną cechą automatu skończonego?
- Czym różni się automat deterministyczny od niedeterministycznego?
Automat może być reprezentowany za pomocą diagramu stanów lub tabeli przejść pomiędzy stanami.
Automaty skończone możemy podzielić na deterministyczne i niedeterministyczne.
Automat deterministyczny
Automatem deterministycznym AD nazywamy piątkę AD = <N,V,M,S,Z>,gdzie:
N –zbiór stanów (alfabet nieterminalny automatu)
V- zbiór wejść (alfabet terminalny automatu)
M –funkcja przejścia automatu tj M:(N x V) &rorr;N (określenie dla danego stanu oraz wejścia stanu nowego do jakiego następuje przejście automatu
S –zbiór stanów początkowych automatu (ustalone symbole nieterminalne)
Z –zbiór stanów końcowych (niepusty zbiór symboli nieterminalnych)
Automat deterministyczny czyta kolejne symbole słowa rozpoczynając w stanie początkowym,po przeczytaniu każdego słowa zmienia swój stan zgodnie z funkcją przejścia. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów końcowych,słowo należy do badanego przez automat języka.
Automat niedeterministyczny
Automatem niedeterministycznym AN nazywamy piątkę AN = <N,V,M,S,Z>,gdzie:
N –zbiór stanów (alfabet nieterminalny automatu)
V- zbiór wejść (alfabet terminalny automatu)
M –relacja przejścia automatu tj M:(N x V) ->2^N (określenie dla danego stanu oraz wejścia stanów nowych do jakich może nastąpić przejście automatu
S –zbiór stanów początkowych automatu (ustalone symbole nieterminalne)
Z –zbiór stanów końcowych (niepusty zbiór symboli nieterminalnych)
Automat niedeterministyczny różni się od deterministycznego tym,że po przeczytaniu danego symbolu może przejść do jednego z kilku różnych stanów.
Dla ciekawych
Dla każdego niedeterministycznego automatu skończonego możemy wygenerować odpowiadający mu deterministyczny automat skończony akceptujący dokładnie te same słowa. Możemy go uzyskać dokonując procesu determinizacji automatu skończonego.
Istnieje cała gama problemów z zakresu projektowania oprogramowania,które da się rozwiązywać przy użyciu automatów skończonych,przykładami takich zastosowań są analizatory leksykalne czy edytory tekstu.
Pytania sprawdzające
Jeżeli masz wątpliwości,zapoznaj się jeszcze raz z powyższymi informacjami.