Deterministyczny automat skończony

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

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} \cdots c_1 \cdot c_0 = c_0 + 2(c_1 + 2(\cdots (c_{n-1} + 2(c_n)) \cdots))

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:

Deterministic Finite-state Automaton.svg
X_0 \rightarrow^0 X_0
X_0 \rightarrow^1 X_1
X_1 \rightarrow^0 X_2
X_1 \rightarrow^1 X_3
X_2 \rightarrow^0 X_4
X_2 \rightarrow^1 X_0
X_3 \rightarrow^0 X_1
X_3 \rightarrow^1 X_2
X_4 \rightarrow^0 X_3
X_4 \rightarrow^1 X_4
stan startowy - X_0
stany akceptujące - tylko X_0

Formalna definicja[edytuj | edytuj kod]

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

  • A jest alfabetem
  • Q jest 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_0\}
  • 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[edytuj | edytuj kod]

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

Algorytm minimalizacji[edytuj | edytuj kod]

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 \not= 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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

  • Automater (pol.) - demonstracja tworzenia minimalnego, deterministycznego automatu skończonego z podanego wyrażenia regularnego