Абстрактный автомат -- ДКА-распознователь

[rederblack]

Попытался разобраться в ДКА. Но есть некоторые непонятности в записи автомата.
Вот что понял на данный момент:
Есть некоторое множество X-входной алфавит т.е. например $X = \{0,1\}$
И множество всех возможных цепочек $X^{*}$ насколько понял это выглядит так
$X^{*} =\{0,1,00,01,10,11,000,001,010,011,100,101,...\}$ и т.д.
Далее есть пустая последовательность $\varepsilon \in X^{*}$, пусть будет $\varepsilon = 0$
Подмножество L называется языком. $L \subset X^{*}$ пусть для примера будет $L = \{00,01,10,11\}$
$\xi \in X^{*}$ например $\xi = 10$, а задача автомата определить $\xi \in L$. Так оно и есть в языке есть элемент 10

И при определении детерминированного конечного автомата - распознавателя запутался.
ДКА - это $\langle X, Y, \delta, y_{0}, F \rangle$ X - алфавит, Y - состояния
и наконец запись$ \delta \colon X \times Y \to Y$ вот тут уже неясно почему получили Y и что эта запись означает!?
$y_{0} \in Y$ - начальное состояние.
$F \subset Y$ - множество допускающих состояний. Но что это за состояния непонятно.
Далее появляется еще одна формула $\hat \delta \colon X^{*} \times Y \to Y$
И 2 красивые записи:
$\forall{y}\in Y (\hat \delta(\varepsilon,y)=y); $
$\forall{y} \in Y \forall{\xi} \in X^{*} \forall{x} \in X (\hat \delta(\xi{x},y)=\delta(x,\hat \delta(\xi,y)))$
Тут я промолчу про запись выше. Просто неясно, что тут происходит
есть еще $\hat \delta(\xi,y_{0}) \in F$
$L=\{ \xi \in X^{*} \mid \hat \delta (\xi,y_{0}) \in F \}$ - в итоге получилась такая запись.

если кто разбирается в таких абстрактных вещах, объясните пожалуйста хотя бы на простых примерах или ту запись со стрелкой, чтобы можно было от чего отталкиваться (я как понял та запись со стрелкой это функция, которая используется дальше в $\delta(\varepsilon,y)$)

Заранее благодарю!

[Maslov]

$\varepsilon$ -- это не 0, а именно пустая цепочка. Т.е., в Вашем случае, $X^* = \{\varepsilon, 0, 1, 01, 00, ...\}$

$\delta$ -- это функция перехода, определяющая новое состояние автомата по его текущему состоянию $y \in Y$ и входному символу $x \in X$. Другими словами, функция перехода задаёт отображение (<входной символ>, <состояние>) $\to$ <новое состояние> ($ \delta \colon X \times Y \to Y$).

Допускающее состояние -- это допустимое конечное состояние автомата при окончании входной цепочки. Т.е., если входная цепочка исчерпана, и автомат находится в одном из допускающих состояний, то входная цепочка распознана данным ДКА.

$\hat \delta$ -- это расширенная функция перехода данного ДКА, заданная на множестве пар (<входная цепочка>, <начальное состояние>) и определяющая конечное состояние ДКА после распознавания входной цепочки.

Первая красивая запись

rederblack в сообщении #283569 писал(а):

$\forall{y}\in Y (\hat \delta(\varepsilon,y)=y); $

просто означает, что пустая цепочка не меняет состояние ДКА.

Вторая красивая запись

rederblack в сообщении #283569 писал(а):

$\forall{y} \in Y \forall{\xi} \in X^{*} \forall{x} \in X (\hat \delta(\xi{x},y)=\delta(x,\hat \delta(\xi,y)))$

означает, что если автомат находится в состоянии $y$, а на вход подаётся цепочка $x_1x_2...x_n$, то состояние автомата после обработки этой цепочки будет
$\hat\delta(x_1x_2...x_n, y) = \delta(x_n, ... \delta(x_2, \delta(x_1, y)) ...)$

Как-то так.

[rederblack]

Maslov
Теперь мне стало более понятно Спасибо большое за пояснение.