По-моему NuShaman где-то говорил, что он не понимает, как работают ДКА, или как их сделать.
Не могу найти то место на форуме...

[html]<a href="https://ru.wikipedia.org/wiki/Детерминированный_конечный_автомат">https://ru.wikipedia.org/wiki/Детерминированный_конечный_автомат</a>[/html]

Представляет интерес математическое определение ДКА русскими буквами (в википедии оно не такое).

---

ДКА это упорядоченная пятёрка <С, с_н, С^К, А, Ф^П>, где

C это множество возможных состояний автомата (вообще, и в различные моменты времени)
с_и - отдельное состояние, идентифицируемое индексом "и".
с_и ∈ С, C = { с_и }, где "и" - различные индексы
если нужно просто упомянуть, что с это одно из состояний,
то есть, не нужно идентифицировать одно из нескольких состояний,
то индекс можно не добавлять.
с ∈ С
С = С^И - множество состояний, это то же самое, что множество идентифицируемых состояний автомата (то есть всех).
С^И не используется в определении ДКА, потому что в этом нет необходимости.
Хотя повод для использования есть: нужно различать С^И и С^К (см. ниже).

с_н - единственное начальное состояние, н - индекс начального состояния, н ∈ И.
с_н ∈ C

C^К - множество конечных состояний
C^К = { с_к }, где K - множество индексов конечных состояний, к ∈ К, К ⊆ И.
C^К ⊆ C, множество конечных состояний является подмножеством всех состояний.

Буквы относятся к некоторому алфавиту:
а ∈ А, А = { а }
Когда нужно показать, что буквы разные, можно приписать индексы, например:
А = { а_и }, А = { а₁, а₂, а₃, ... , а_я}
где "я" - индекс последнего символа алфавита

Для кириллического алфавита
а₁ = "А", а₂ = "Б", а₃ = "В", ... , а₃₃ = "Я".

Ф^П это функция переходов, записываемая как
с_м+1 = Ф^П(с_м, а)
с_м+1 - состояние в следующий момент ("м+1") времени
с_м - состояние в текущий момент ("м") времени
а - входная буква (на момент времени "м"), а = а_м (но записывать это явно нет необходимости, так как мы стараемся везде сократить запись)

буква П своей формой (внешним видом) удачно символизирует переход - подъем, перемещение и приземление.
---

см. также
Теория автоматов.
Преобразование НКА в ДКА, Алгоритм Томпсона
Преобразование ДКА в ассемблерный код

Отредактировано Лис (2024-10-03 03:11:39)