Deterministyczny automat skończony

Z Wikipedii

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.

[edytuj] 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} \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:

$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

[edytuj] Formalna definicja

Deterministyczny automat skończony może zostać jednoznacznie opisany przez 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

[edytuj] Zobacz też

Kategoria: Teoria automatów

We provide Linux to the World

Deterministyczny automat skończony

Z Wikipedii

[edytuj] Przykład

[edytuj] Formalna definicja

[edytuj] Zobacz też

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach