Deterministyczny automat skończony

Deterministyczny Automat Skończony (DFA)

Deterministyczny automat skończony (DFA) to abstrakcyjna maszyna z ograniczoną liczbą stanów, która przetwarza symbole słowa. Rozpoczyna w stanie początkowym i po przeczytaniu każdego symbolu przechodzi do nowego stanu, zgodnie z funkcją przejścia. Słowo należy do języka rozpoznawanego przez automat, jeśli po jego przetworzeniu automat znajduje się w stanie akceptującym.

Budowa DFA

DFA można przedstawić w formie tabeli przejść lub diagramu. Przykładowo, automat rozpoznający słowa binarne podzielne przez 5 można zbudować, wykorzystując obliczenia w arytmetyce modulo 5. Automatyczne przejścia dla cyfr 0 i 1 prowadzą do różnych stanów, a stan akceptujący to ten reprezentujący podzielność przez 5.

Formalna Definicja

DFA jest zdefiniowany przez pięć elementów: $(A,\; Q,\; q\_0,\; F,\; d)$, gdzie:

• $A$ – skończony alfabet wejściowy.
• $Q$ – skończony zbiór stanów.
• $q\_0$ – stan początkowy.
• $F$ – zbiór stanów akceptujących.
• $d$ – funkcja przejścia, określająca nowy stan po przeczytaniu symbolu.

Minimalizacja DFA

Każdy deterministyczny automat skończony ma unikalny automat minimalny, akceptujący ten sam język.

Algorytm Minimalizacji

1. Usuń stany nieosiągalne ze stanu początkowego.
2. Utwórz tabelę par stanów.
3. Zaznacz pary, gdzie jeden stan jest akceptujący, a drugi nie.
4. Sprawdź nieoznakowane pary stanów pod kątem ich przejść i oznaczaj je, jeśli są takie same.
5. Po zakończeniu, niezaznaczone pary stanów łączone są w jeden stan.

Przykład Minimalizacji

W przypadku automatu rozpoznającego liczby binarne podzielne przez 5, wszystkie stany są osiągalne ze stanu początkowego. Po utworzeniu tabeli i zaznaczeniu odpowiednich par stanów okazuje się, że pierwotny automat jest już minimalny.