Самопроверяющийся конечный автомат - Self-verifying finite automaton

В теория автоматов, а самопроверяющийся конечный автомат (SVFA) - особый вид недетерминированный конечный автомат (NFA) с симметричным типом недетерминизма, вводимым Громкович и Шнитгер.^[1]Как правило, при самопроверяющемся недетерминизме каждый путь вычисления завершается любым из трех возможных ответов:да, нет, и я не знаю.Для каждой входной строки никакие два пути не могут давать противоречивые ответы, а именно оба ответа. да и нет на одном входе невозможны. По крайней мере, один путь должен давать ответ да или же нет, а если это да тогда строка считается принятой. VFA принимает тот же класс языков, что и детерминированные конечные автоматы (DFA) и NFA, но имеют разные сложность состояния.

Формальное определение

SVFA формально представлена 6-кратный,А=(Q, Σ, Δ, q₀, F_а, F_р) такой, что (Q, Σ, Δ, q₀, F_а)является NFA,и F_а, F_р непересекающиеся подмножества Q.Для каждого слова ш = а₁а₂ … А_п, а вычисление это последовательность состоянийр₀,р₁, …, р_п, в Q со следующими условиями:

1. р₀ = q₀
2. р_{я + 1} ∈ Δ (р_я, а_{я + 1}), за я = 0,…, n − 1.

Если r_п ∈ F_а то вычисление принимается, и если r_п ∈ F_р то вычисление отклоняется. Существует требование, чтобы для каждого шесть хотя бы одно принимающее вычисление или хотя бы одно отклоняющее вычисление, но не оба.

Полученные результаты

Каждый DFA является SVFA, но не наоборот. Пигиццини^[2]доказал, что для каждого SVFA из п состояний, существует эквивалентный ДКА ${ Displaystyle г (п) = тета (3 ^ {п / 3})}$ состояний. Кроме того, для каждого положительного целого числа п, существует п-состояние SVFA такое, что минимальный эквивалентный DFA имеет ровно ${ Displaystyle г (п)}$ состояния.

Другие результаты на сложность состояния SVFA были получены Йирасковой и ее коллегами.^[3][4]

Рекомендации