Applications of Finite State Machines (Алексей Чеусов, LVEE-2019) — различия между версиями

Текущая версия на 13:58, 24 октября 2025

Докладчик: Алексей Чеусов

In this presentation we define the finite state automata (FSA), Moore and Mealy machines, and Finite State Transducers. Weighted and stochastic finite state machines are described. Also, a few well-known and custom algorithms based on finite state machines, are described.

Видео

on youtube

Презентация

Thesis

Начать следует с определений и теорем, хорошо знакомых любому выпускнику ВУЗ-а по технической специальности.

Определение: Недетерминированным конечным автоматом (НКА) называется пятёрка <I,S,Q,F,δ>, где:

I — конечное непустое множество символов (алфавит);
S — конечное непустое множество состояний;
Q — множество стартовых состояний, Q ⊆ S;
F — множество конечных состояний, F ⊆ S;
δ — отношение переходов δ ⊆ S × I × S (или, иначе, δ: S × I → ).

Языком КА является множество различных последовательностей символов алфавита, допускаемых конечным автоматом, то есть, цепочек символов вдоль пути от стартового до конечного состояния КА.

Определение: Регулярный язык над алфавитом Σ определяется следующим образом:

Пустой язык ∅ и язык {ε}, состоящий из пустой строки, являются регулярными языками;
{a}, где a ∈ Σ, является регулярным языком;
Если A и B — регулярные языки, то A ∪ B (объединение), A • B (конкатенация) и (звезда Клини) являются регулярными языками;
Никакие другие языки над Σ не являются регулярными.

Этот формализм даёт нам так называемые «регулярные выражения».

Определение: Детерминированным конечным автоматом (ДКА) является пятёрка <I,S,q,F,δ>, где:

I — конечное непустое множество символов (алфавит);
S — конечное непустое множество состояний;
q — стартовое состояние, q ∈ S;
F — множество конечных состояний, F ⊆ S;
δ — функция переходов: δ: S × I → S.

Теоремы:

НКА и ДКА — эквивалентные формализмы, то есть для каждого НКА существует эквивалентный ему ДКА; обратное верно по определению.
В общем случае ДКА может быть экспоненциально больше (по количеству состояний) по сравнению с эквивалентным ему НКА.
Для любого ДКА существует только один (с точностью до изоморфизма) минимальный ДКА, эквивалентный ему.
Регулярные языки и конечные автоматы — эквивалентные формализмы, то есть для любого конечного автомата существует эквивалентный ему регулярный язык и наоборот.
Конечные автоматы замкнуты относительно операций объединения, вычитания, пересечения, дополнения и звезды Клини.

Алгоритм построения ДКА из НКА представлен ниже.

Вход:  NFA = <I,S,Q,F,δ>
Выход: DFA = <I,S′,q′,F′,δ′>

δ′ := ∅, q′ := {s | s ∈ Q}, S′ := {q′}
seen := {q′}, queue := [q′]

пока queue ≠ ∅:
    src_states ← queue
    для каждого i ∈ I:
        trg_states := {sᵗʳᵍ | (sˢʳᶜ,i,sᵗʳᵍ) ∈ δ, sˢʳᶜ ∈ src_states}
        если trg_states ≠ ∅:
            δ′ ← (src_states, i, trg_states)
            S′ ← trg_states
            если trg_states ∉ seen:
                queue ← trg_states
                seen ← trg_states

F′ := {state_set ∈ S′ | ∃ s ∈ state_set, s ∈ F}

nfa2dfa algorithm (также известен как «Subset construction»)

Введём два дополнительных оператора:

R — оператор инвертирования. L(R(KA)) = { inverse(w) | w ∈ L(KA) }
D — оператор построения ДКА по НКА.

Алгоритм Бжозовского построения минимального ДКА по НКА:

Замечание: В отличие от большинства других алгоритмов построения минимального ДКА, алгоритм Бжозовского строит минимальный ДКА по НКА!

Алгоритм проверки, входит ли строка в язык ДКА:

Вход:  DFA = <I,S,q,F,δ>, Text = [t₁, t₂ … tₙ], tᵢ ∈ I
Выход: true или false

state := q
для i от 1 до n:
    если δ определена на (state, tᵢ):
        state := δ(state, tᵢ)
    иначе:
        вернуть false
вернуть (state ∈ F)

# Сопоставление строки с ДКА
# Сложность алгоритма: O(n)

Алгоритм проверки, входит ли строка в язык НКА.

Вход:  NFA = <I,S,Q,F,δ>, Text = [t₁, t₂ … tₙ], tᵢ ∈ I
Выход: true или false

states := Q
для i от 1 до n и пока states ≠ ∅:
    states := { trg | (src, tᵢ, trg) ∈ δ, src ∈ states }
вернуть (∃ s ∈ states, s ∈ F)

# Сопоставление строки с НКА
# Сложность алгоритма: O(n × |S|)

Область применения взвешенных конечно-автоматных преобразователей: распознавание речи, синтез речи, распознавание символов, машинный перевод, различные задачи обработки естественного языка, включая синтаксический анализ и моделирование языка, распознавание образов и вычислительная биология.

Задачи, решаемые с помощью конечных автоматов:

Исправление ошибок OCR-распознавания CUSIP. Идея алгоритма заключается в построении взвешенного конечно-автоматного преобразователя. В нём состояния соответствуют значению контрольной суммы (по модулю 10), рассчитанной для определённого символа (8 групп по 10 состояний в каждой), а переходы между группами состояний соответствуют символам CUSIP. Переходы из состояний 8-й группы в конечное состояние соответствуют символу контрольной суммы. Входным алфавитом является множество наблюдаемых (распознанных) символов. Выходным алфавитом — множество символов, допустимых в CUSIP. При этом выходной вес на переходе соответствует правильному (исправленному) символу CUSIP. Вес же перехода — это условная вероятность правильного символа при определённом наблюдаемом. Таким образом, путь с максимальным произведением заданных на переходах условных вероятностей и даёт нам способ исправления неправильно распознанных символов CUSIP. При этом правильность контрольной суммы CUSIP обеспечивается структурой конечно-автоматного преобразователя.
Исправление ошибок OCR-распознавания IBAN. Подход, который можно использовать для этой задачи, ровно тот же, что и в задаче корректирования CUSIP. Разница заключается лишь в том, что КА строится для другой контрольной суммы (mod 97) и с использованием регулярных выражений, задающих форму IBAN для различных стран Европы. Такой КА получится достаточно большим.
Наиболее простым способом применения КА является проектирование программного обеспечения, в частности проектирование классов при использовании объектно-ориентированной парадигмы. Жизненный цикл объекта некоторого класса представляется в виде КА, задающего его поведение. При этом стартовое состояние КА представляет собой состояние объекта в момент после его создания конструктором по умолчанию, а переходы соответствуют вызовам определённых функций в моменты, когда объект находится в определённых состояниях. Этот подход даёт возможность тестировать поведение объекта (и, в общем случае, ПО) в процессе его жизни. Такого рода тестирование заключается в покрытии таблицы переходов КА.
Задача извлечения именованных сущностей из текста также может быть решена с использованием взвешенных конечных автоматов. Идея такого алгоритма заключается в том, что классификация производится пословно на классах B, I, O, E, S (при использовании BIOES-нотации), а затем производится выбор из всех возможных цепочек только тех, которые согласуются с BIOES-нотацией, которую можно задать с помощью КА. При этом переходы КА взвешены вероятностями, полученными классификационным алгоритмом, а значит появляется возможность выбрать наиболее вероятную последовательность меток B, I, E, S и O. Этот подход является по сути алгоритмом выбора цепочки меток, соответствующей максимальной совместной вероятности набора меток, при этом множество цепочек, из которых производится отбор, полностью соответствует BIOES-нотации.
Автоматы Мура можно использовать, например, для задачи сопоставления текста с образцами с сохранением информации о том, какой именно набор образцов «сработал» на заданном тексте. Для решения данной задачи при использовании ДКА необходимо воспользоваться информацией о том, из каких состояний исходного НКА «сформировано» состояние ДКА. Эта информация используется для формирования символа выходного алфавита, соответствующего «конечному» состоянию, которое соответствует любому набору исходных регулярных выражений. Потенциально выходной алфавит может содержать элементов, где n — количество исходных регулярных выражений.

Примечания и ссылки

Plays:72 Comments:1