Automaty

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
S11 S1
S10 S2
S21 S2
S20 S1

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

  • Co jest główną cechą automatu skończonego?
  • Czym różni się automat deterministyczny od niedeterministycznego?

Jeżeli masz wątpliwości,zapoznaj się jeszcze raz z powyższymi informacjami.