Конечный автомат можно разделить на два типа —
- Детерминированный конечный автомат (DFA)
- Недетерминированный конечный автомат (NDFA / NFA)
Детерминированный конечный автомат (DFA)
В DFA для каждого входного символа можно определить состояние, в которое машина перейдет. Следовательно, это называется Детерминированный Автомат . Поскольку оно имеет конечное число состояний, машина называется « Детерминированный конечный автомат» или « Детерминированный конечный автомат».
Формальное определение DFA
DFA может быть представлен 5-кортежем (Q, ∑, δ, q 0 , F), где —
-
Q — конечное множество состояний.
-
∑ — это конечный набор символов, называемый алфавитом.
-
δ — функция перехода, где δ: Q × ∑ → Q
-
q 0 — начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).
-
F — множество конечных состояний / состояний Q (F ⊆ Q).
Q — конечное множество состояний.
∑ — это конечный набор символов, называемый алфавитом.
δ — функция перехода, где δ: Q × ∑ → Q
q 0 — начальное состояние, из которого обрабатывается любой вход (q 0 ∈ Q).
F — множество конечных состояний / состояний Q (F ⊆ Q).
Графическое представление DFA
DFA представлен орграфами, которые называются диаграммой состояний .
- Вершины представляют состояния.
- Дуги, помеченные входным алфавитом, показывают переходы.
- Начальное состояние обозначается пустой единственной входящей дугой.
- Конечное состояние обозначено двойными кружками.
пример
Пусть детерминированный конечный автомат будет →
- Q = {a, b, c},
- ∑ = {0, 1},
- q 0 = {а},
- F = {c} и
Функция перехода δ, как показано в следующей таблице —
| Современное состояние | Следующее состояние для ввода 0 | Следующее состояние для ввода 1 |
|---|---|---|
| б | ||
| б | с | |
| с | б | с |
Его графическое представление будет следующим: