Самопроверяющийся конечный автомат

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

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

SVFA формально представлен из 6 кортежем А = ( Q , Σ , Δ, q ₀ , F _а , F _р ) такой, что ( Q , Σ , Δ, q ₀ , F _a ) является НФА , и F _a , F _r — непересекающиеся подмножества Q . Для каждого слова w = a ₁ a ₂ … _an , Вычисление — это последовательность состояний r ₀ ,r ₁ , …, r _n , в Q со следующими условиями:

р ₀ = д ₀
r _i+1 ∈ Δ( r _i , a _i+1 ), для i = 0, …, n−1 .

Если r _n ∈ F _a, то вычисление принимается: и если r _n ∈ F _r , то вычисление отклоняется. Существует требование, чтобы для каждого w существует хотя бы одно принимающее вычисление или хотя бы одно отклоняющее вычисление но не оба.

Результаты

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

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

Ссылки

^ Хромкович, Юрай; Шнитгер, Георг (2001). «О возможностях Лас-Вегаса в плане сложности односторонней связи, OBDD и конечных автоматов» . Информация и вычисления . 169 (2): 284–296. дои : 10.1006/inco.2001.3040 . ISSN 0890-5401 .
^ Йираскова, Галина; Пигиццини, Джованни (2011). «Оптимальное моделирование самопроверяющихся автоматов детерминированными автоматами». Информация и вычисления . 209 (3): 528–535. дои : 10.1016/j.ic.2010.11.017 . ISSN 0890-5401 .
^ Йираскова, Галина (2016). «Самопроверяющиеся конечные автоматы и сложность описания» (PDF) . Описательная сложность формальных систем . Конспекты лекций по информатике. Том. 9777. стр. 29–44. дои : 10.1007/978-3-319-41114-9_3 . ISBN 978-3-319-41113-2 . ISSN 0302-9743 .
^ Йирасек, Йозеф Штефан; Жираскова Галина; Сабари, Александр (2015). «Операции над самопроверяющимися конечными автоматами». Информатика – теория и приложения . Конспекты лекций по информатике. Том. 9139.стр. 231–261. дои : 10.1007/978-3-319-20297-6_16 . ISBN 978-3-319-20296-9 . ISSN 0302-9743 .

[HromkovičSchnitger2001-1] Хромкович, Юрай; Шнитгер, Георг (2001). «О возможностях Лас-Вегаса в плане сложности односторонней связи, OBDD и конечных автоматов» . Информация и вычисления . 169 (2): 284–296. дои : 10.1006/inco.2001.3040 . ISSN 0890-5401 .

[JiráskováPighizzini2011-2] Йираскова, Галина; Пигиццини, Джованни (2011). «Оптимальное моделирование самопроверяющихся автоматов детерминированными автоматами». Информация и вычисления . 209 (3): 528–535. дои : 10.1016/j.ic.2010.11.017 . ISSN 0890-5401 .

[Jirásková2016-3] Йираскова, Галина (2016). «Самопроверяющиеся конечные автоматы и сложность описания» (PDF) . Описательная сложность формальных систем . Конспекты лекций по информатике. Том. 9777. стр. 29–44. дои : 10.1007/978-3-319-41114-9_3 . ISBN 978-3-319-41113-2 . ISSN 0302-9743 .

[JirásekJirásková2015-4] Йирасек, Йозеф Штефан; Жираскова Галина; Сабари, Александр (2015). «Операции над самопроверяющимися конечными автоматами». Информатика – теория и приложения . Конспекты лекций по информатике. Том. 9139.стр. 231–261. дои : 10.1007/978-3-319-20297-6_16 . ISBN 978-3-319-20296-9 . ISSN 0302-9743 .

[1]

[2]

[3]

[4]