Начало
Учебные материалы
Вычислительные основы
Реальные компьютеры vs. модели вычислений Детерминированный конечный автомат Машина Тьюринга Нормальный алгоритм Маркова Теория рекурсивных функций * Практическое использование
Детерминированный конечный автомат
1. `Sigma` – алфавит, то есть конечное множество входных символов;
2. `Q` – конечное множество состояний;
3. `q_0 in Q` – начальное состояние;
4. `delta: Q xx Sigma -> Q` – функция перехода, то есть «программа», которая исполняет детерминированный конечный автомат. `delta` вычисляет следующее состояние `p = delta(q, a)`, где `p, q in Q, a in Sigma`;
5. `F sube Q` – множество финальных состояний (для автомата-распознавателя)
Для автомата-преобразователя вместо `F` нужно задать функцию выхода `lambda: Q -> Phi` (автомат Мура) или `lambda: Q xx Sigma -> Phi` (автомат Мили), где `Phi` - множество выходных символов.
--
Для того чтобы увидеть, что ДКА, заданный `А`, принимает строку `w`, мы «выполняем» `А` на
`w = a_1 a_2 ... a_n` следующим образом: `delta(q_0, a_1) = q_1`, `delta(q_1, a_2) = q_2` ...
`delta(q_{n-1}, a_n) = q_n`. `A` принимает `w` тогда и только тогда, когда `q_n in F`,
то есть если `q_n` является одним из финальных (принимающих) состояний. В противном случае мы говорим, что ДКА отклоняет `w`.
--
Предположим, что мы хотим спроектировать детерминированный конечный
автомат для языка L01, в котором допустимы только цепочки символов, содержащие 01.
Пусть `Sigma = {0, 1}`, `Q = {q_0, q_1, q_2}` и `F = {q_1}`. Существует два способа
представить `delta`: в форме диаграммы переходов либо в форме таблицы переходов.
```width:300px|dot
digraph L01 {
graph [rankdir = "LR"];
node[shape = none]; start [label=""];
node[shape = doublecircle]; q1 [label=<
<i>q</i><sub>1</sub>
>];
node[shape = circle]; q0 [label=<
<i>q</i><sub>0</sub>
>] q2 [label=<
<i>q</i><sub>2</sub>
>];
start->q0
q0 -> q0 [label="1"]
q0 -> q2 [label="0"]
q2 -> q2 [label="0"]
q2 -> q1 [label="1"]
q1 -> q1 [label="0,1"]
}
```
||.draw||_ |0|1
--|--|--
`q_0`|`q_2`|`q_0`
`q_1`|`q_1`|`q_1`
`q_2`|`q_2`|`q_1`
--
Недетерминированный конечный автомат (НКА, nondeterministic finite automaton, NFA)
определяется аналогично ДКА, за исключением того, что переходная функция `delta` становится переходным отношением, то есть
`delta in Q xx Sigma xx Q`, то есть на одной и той же паре `(q, a)` может существовать более
одного возможного нового состояния (или ни одного).
Также мы можем смотреть на `delta` как на `delta : Q xx Sigma -> P(Q)`, где `P(Q)` – это множество подмножеств `Q`.
НДКА для языка Ln - `n`-ый символ с конца равен 1.
```width:500px|dot
digraph Ln {
graph [rankdir = "LR"];
node[shape = none]; start [label=""] skip [label="..."];
node[shape = doublecircle]; qn [label=<
<i>q<sub>n</sub></i>
>];
node[shape = circle]; q0 [label=<
<i>q</i><sub>0</sub>
>] q1 [label=<
<i>q</i><sub>1</sub>
>] q2 [label=<
<i>q</i><sub>2</sub>
>] fail [label=<
<i>q<sub>err</sub></i>
>];
start->q0
q0 -> q0 [label="0,1"]
q0 -> q1 [label="1"]
q1 -> q2 [label="0,1"]
q2 -> skip [label="0,1"]
skip -> qn [label="0,1"]
qn -> fail [label="0,1"]
fail -> fail [label="0,1"]
}
```
--
Теорема *Детерминированный и недетерминированный конечные автоматы являются эквивалентными.*
Очевидно, что ДКА – это особый случай НКА.
Таким образом, остается доказать, что каждый НКА может быть перепроектирован как ДКА, что осуществляется через построение подмножеств.
Сначала мы принимаем допущение, что НКА `N` не имеет `varepsilon`-переходов. Пусть `M` это ДКА, и тогда `Q_M = P(Q_N)`,
где `P(Q_N)` – состоит из всех возможных подмножеств множеств `Q_N`, и `delta_M(Q, a) := bigcup_{q in Q} delta_N(q, a)`,
где `Q in P(Q_N)`.
Также `F_M = {Q in P(Q_N) : Q cap F_N != emptyset}` и `(q_M)_0 := {(q_N)_0}`.
Если `N` имеет `varepsilon`-переходы, то `delta_M(Q, a) := bigcup_{q in Q} varepsilon-closure(delta_N(q, a))`.
--
Отметим, что происходит экспоненциальный рост состояний, поскольку `|P(Q_N)| = 2^{|QN|}`.
Мы симулируем более выразительную модель вычисления (НКА) с помощью более ограниченной (ДКА).
--
Рассмотрим пример преобразования из НКА для L2 (L2 – это множество строк, где предпоследний символ равен 0) в ДКА.
```width:400px|dot
digraph L2 {
graph [rankdir = "LR"];
node[shape = none]; start [label=""];
node[shape = doublecircle]; q2 [label=<
<i>q</i><sub>2</sub>
>];
node[shape = circle]; q0 [label=<
<i>q</i><sub>0</sub>
>] q1 [label=<
<i>q</i><sub>1</sub>
>] q3 [label=<
<i>q</i><sub>3</sub>
>];
start->q0
q0 -> q0 [label="0,1"]
q0 -> q1 [label="0"]
q1 -> q2 [label="0,1"]
q2 -> q3 [label="0,1"]
q3 -> q3 [label="0,1"]
}
```
ДКА для L2 (7 состояний справа недостижимы, их можно убрать)
```width:800px|dot
digraph L2f {
graph [rankdir = "LR"];
node[shape = none]; start [label=""];
node[shape = doublecircle]; q2 [label=<
<i>q</i><sub>2</sub>
>] q02 [label=<
<i>q</i><sub>0,2</sub>
>] q012 [label=<
<i>q</i><sub>0,1,2</sub>
>] q12 [label=<
<i>q</i><sub>1,2</sub>
>] q23 [label=<
<i>q</i><sub>2,3</sub>
>] q023 [label=<
<i>q</i><sub>0,2,3</sub>
>] q0123 [label=<
<i>q</i><sub>0,1,2,3</sub>
>] q123 [label=<
<i>q</i><sub>1,2,3</sub>
>];
node[shape = circle]; q0 [label=<
<i>q</i><sub>0</sub>
>] q1 [label=<
<i>q</i><sub>1</sub>
>] q3 [label=<
<i>q</i><sub>3</sub>
>] q01 [label=<
<i>q</i><sub>0,1</sub>
>] q03 [label=<
<i>q</i><sub>0,3</sub>
>] q013 [label=<
<i>q</i><sub>0,1,3</sub>
>] q13 [label=<
<i>q</i><sub>1,3</sub>
>];
start->q0
q0 -> q0 [label="1"]
q0 -> q01 [label="0"]
q01 -> q02 [label="1"]
q01 -> q012 [label="0"]
q02 -> q03 [label="1"]
q02 -> q013 [label="0"]
q03 -> q03 [label="1"]
q03 -> q013 [label="0"]
q012 -> q023 [label="1"]
q012 -> q0123 [label="0"]
q013 -> q023 [label="1"]
q013 -> q0123 [label="0"]
q023 -> q03 [label="1"]
q023 -> q013 [label="0"]
q0123 -> q023 [label="1"]
q0123 -> q0123 [label="0"]
q023 -> q123 [dir=none color=white]
q1 -> q2 [label="0,1"]
q2 -> q3 [label="0,1"]
q23->q3 [label="0,1"]
q123->q23 [label="0,1"]
q13->q23 [label="0,1"]
q12->q23 [label="0,1"]
}
```
--
Описанный КА использует только одну ячейку памяти, в которой хранится текущее состояние
и может только распознавать или преобразовывать цепочки символов.
Если добавить в КА возможность использовать память и выполнять действия, то можно описать любое вычислительное устройство (компьютер).
В функцию перехода добавляются параметры, связанные с текущим состоянием памяти, а результат
включает не только изменение состояния, но и изменение памяти. Для диаграмм, описывающих КА общего вида, используется, например, UML.
--
Различают конечные автоматы
* с конечной памятью (можно свести к КА без памяти, включив состояние памяти в номер состояния,
что существенно усложняет определение КА);
* с бесконечной памятью (рассматривают обычно КА с памятью организованной в форме стека, такие КА используются в компиляторах).
Объекты в ООП рассматриваются как КА с памятью.
---
##### Задания для практики
1. Формат числа описывается следующей схемой
Определите ДКА для ввода числа
2. Определите ДКА, проверяющий что строка из букв a,b,c содержит буквы a и b.
3. Определите ДКА, проверяющий что строка из букв a,b,c имеет длину 3 и является перестановкой букв a,b,c.
--
[Редактор и исполнитель конечных автоматов](http://fsm-simulator.info/App/Designer)
