Deterministyczny automat skończony

Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to abstrakcyjna maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa, po przeczytaniu każdego zmieniając swój stan na stan będący wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), słowo należy do języka regularnego, do rozpoznawania którego jest zbudowana.

Deterministyczny automat skończony, podobnie jak inne automaty skończone może być reprezentowany za pomocą tabeli przejść pomiędzy stanami lub diagramu stanów.

Przykład

Zbudujmy na przykład maszynę rozpoznającą takie słowa nad alfabetem binarnym (reprezentujące liczby, przy najbardziej znaczącej z lewej strony), które są podzielne przez 5.

Żeby zbudować tę maszynę skorzystajmy z faktu, że:

$w\cdot 0=2w,$

$w\cdot 1=2w+1$ (wartość liczby to ostatnia cyfra plus dwa razy wartość liczby zbudowanej z pozostałych cyfr),

czyli:

$c_{n}\cdot c_{n-1}\dots c_{1}\cdot c_{0}=c_{0}+2(c_{1}+2(\dots (c_{n-1}+2(c_{n}))\dots )).$

Ale jako że obchodzi nas nie wynik, a jedynie jego podzielność przez 5, możemy wykonywać obliczenia w arytmetyce modulo 5.

Czyli zaczynamy od stanu $X_{0},$ i po przeczytaniu każdej cyfry $c_{i}$ przechodzimy ze stanu $X_{j}$ do stanu $X_{2j+c_{i}\,\mathrm {mod} \,5}.$ Jeśli po przeczytaniu całego słowa jesteśmy w stanie $X_{0},$ oznacza to, że reszta z dzielenia słowa przez 5 wynosi 0, a więc słowo jest podzielne przez 5:

$X_{0}\to ^{0}X_{0}$

$X_{0}\to ^{1}X_{1}$

$X_{1}\to ^{0}X_{2}$

$X_{1}\to ^{1}X_{3}$

$X_{2}\to ^{0}X_{4}$

$X_{2}\to ^{1}X_{0}$

$X_{3}\to ^{0}X_{1}$

$X_{3}\to ^{1}X_{2}$

$X_{4}\to ^{0}X_{3}$

$X_{4}\to ^{1}X_{4}$

stan startowy – $X_{0}$

stany akceptujące – tylko $X_{4}.$

Formalna definicja

Deterministyczny automat skończony może zostać jednoznacznie opisany przez piątkę $(A,Q,q_{0},F,d),$ gdzie

• $A$ jest skończonym alfabetem wejściowym.
• $Q$ jest skończonym zbiorem stanów.
• $q_{0}$ jest wyróżnionym stanem początkowym należącym do $Q.$
• $F$ jest zbiorem stanów akceptujących (końcowych), będącym podzbiorem $Q.$
• $d$ jest funkcją przejścia, przypisującą parze $(q,a)$ nowy stan $p,$ w którym znajdzie się automat po przeczytaniu symbolu $a$ w stanie $q.$

Funkcja $d$ może być częściowo określona. To znaczy mogą istnieć takie pary $(q,a),$ dla których nie jest określony nowy stan.

W powyższym przykładzie mamy:

• $A=\{0,1\}$
• $Q=\{X_{0},X_{1},X_{2},X_{3},X_{4}\}$
• $q_{0}=X_{0}$
• $F=\{X_{4}\}$
• $d{:}$

$d(X_{0},0)=X_{0}$

$d(X_{0},1)=X_{1}$

$d(X_{1},0)=X_{2}$

$d(X_{1},1)=X_{3}$

$d(X_{2},0)=X_{4}$

$d(X_{2},1)=X_{0}$

$d(X_{3},0)=X_{1}$

$d(X_{3},1)=X_{2}$

$d(X_{4},0)=X_{3}$

$d(X_{4},1)=X_{4}.$

Minimalizacja

Do każdego deterministycznego automatu skończonego istnieje jednoznaczny automat minimalny, który akceptuje ten sam język.

Algorytm minimalizacji

1. Usuń z automatu wszystkie stany, które nie są osiągalne ze stanu początkowego.

2. Utwórz tabelę par stanów automatu $\{X_{i},X_{j}\},$ gdzie $X_{i}\neq X_{j}.$

2.1. Zaznacz wszystkie pary stanów, gdzie $X_{i}\in F,$ a $X_{j}\notin F.$

2.2. Dla każdej nie zaznaczonej jeszcze pary stanów oraz dla każdego elementu $a\in A$ sprawdź, czy para $\{d(X_{i},a),d(X_{j},a)\}$ jest zaznaczona. Jeśli tak, zaznacz również $\{X_{i},X_{j}\}.$

2.3. Powtarzaj krok 2.2. tak długo, dopóki żadna zmiana w tabeli nie będzie już możliwa.

2.4. Każda para, która pozostała niezaznaczona, zostaje stopiona do jednego stanu.

Przykład

minimalizacja automatu rozpoznającego wyrazy binarne podzielne przez 5 (zobacz przykład automatu powyżej)

Krok 1: Wszystkie stany automatu są osiągalne ze stanu początkowego $X_{0}.$

Krok 2: Tworzenie tabeli

$X_{1}$
$X_{2}$
$X_{3}$
$X_{4}$
	$X_{0}$	$X_{1}$	$X_{2}$	$X_{3}$

Krok 2.1: Zaznaczamy wszystkie pary stanów, gdzie $X_{i}\in F,$ a $X_{j}\notin F.$

$X_{1}$	[0]
$X_{2}$	[0]
$X_{3}$	[0]
$X_{4}$	[0]
	$X_{0}$	$X_{1}$	$X_{2}$	$X_{3}$

Kroki 2.2 – 2.3:

• Zaznaczamy parę $\{X_{2},X_{3}\},$ ponieważ $d(X_{2},1)=X_{0}$ oraz $d(X_{3},1)=X_{2},$ a para $\{X_{0},X_{2}\}$ jest już zaznaczona. [1]
• Zaznaczamy parę $\{X_{1},X_{2}\},$ ponieważ $d(X_{1},1)=X_{3}$ oraz $d(X_{2},1)=X_{0},$ a para $\{X_{0},X_{3}\}$ jest już zaznaczona. [2]
• Zaznaczamy parę $\{X_{2},X_{4}\},$ ponieważ $d(X_{2},1)=X_{0}$ oraz $d(X_{4},1)=X_{4},$ a para $\{X_{0},X_{4}\}$ jest już zaznaczona. [3]
• Zaznaczamy parę $\{X_{1},X_{3}\},$ ponieważ $d(X_{1},0)=X_{2}$ oraz $d(X_{3},0)=X_{1},$ a para $\{X_{1},X_{2}\}$ jest już zaznaczona. [4]
• Zaznaczamy parę $\{X_{1},X_{4}\},$ ponieważ $d(X_{1},0)=X_{2}$ oraz $d(X_{4},0)=X_{3},$ a para $\{X_{2},X_{3}\}$ jest już zaznaczona. [5]
• Zaznaczamy parę $\{X_{3},X_{4}\},$ ponieważ $d(X_{3},0)=X_{1}$ oraz $d(X_{4},0)=X_{3},$ a para $\{X_{1},X_{3}\}$ jest już zaznaczona. [6]

$X_{1}$	[0]
$X_{2}$	[0]	[2]
$X_{3}$	[0]	[4]	[1]
$X_{4}$	[0]	[5]	[3]	[6]
	$X_{0}$	$X_{1}$	$X_{2}$	$X_{3}$

Krok 2.4: Wszystkie pary stanów automatu zostały zaznaczone. Z tego wynika, że pierwotny automat jest już automatem minimalnym.

Zobacz też

• automat Büchiego
• automat Mealy’ego
• automat Moore’a
• maszyna Turinga
• niedeterministyczny automat skończony

Linki zewnętrzne

• Automater. fretka.porubis.pl. [zarchiwizowane z tego adresu (2010-09-01)]. (pol.) – demonstracja tworzenia minimalnego, deterministycznego automatu skończonego z podanego wyrażenia regularnego