Однозначный конечный автомат - Unambiguous finite automaton

В теория автоматов, однозначный конечный автомат (УФА) это недетерминированный конечный автомат (NFA) так, что каждое слово имеет не более одного пути приема. Каждый детерминированный конечный автомат (DFA) - это UFA, но не наоборот. DFA, UFA и NFA распознают один и тот же класс формальные языки. С одной стороны, NFA может быть экспоненциально меньше, чем эквивалентный DFA. С другой стороны, некоторые проблемы легко решаются на DFA, а не на UFA. Например, учитывая автомат А, автомат А′ который принимает дополнение А можно вычислить за линейное время, когда А является DFA, неизвестно, можно ли это сделать за полиномиальное время для UFA. Следовательно, UFA представляют собой смесь миров DFA и NFA; в некоторых случаях они приводят к меньшим автоматам, чем DFA, и более быстрым алгоритмам, чем NFA.

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

An NFA представлен формально 5-кратный, А=(Q, Σ, Δ, q0, F) .An УФА является такой NFA, что для каждого слова ш = а1а2 … Ап, существует не более одной последовательности состояний р0,р1, …, рп, в Q со следующими условиями:

  1. р0 = q0
  2. ря + 1 ∈ Δ (ря, ая + 1), за я = 0,…, n − 1
  3. рп ∈ F.

На словах эти условия гласят, что если ш принимается А, существует ровно один путь приема, то есть один путь от начального состояния до конечного состояния, помеченный ш.

Пример

Позволять L быть набором слов над алфавит {а,б} чей п-я последняя буква - это а. На рисунках показаны DFA и UFA, принимающие этот язык для п = 2.

Детерминированный автомат (DFA) для языка L за п = 2
Однозначный конечный автомат (УФА) для языка L за п = 2

Минимальный прием DFA L имеет 2п состояний, по одному для каждого подмножества {1 ...п}. Есть УФА п+1 штаты, которые принимают L: угадывает п-я последняя буква, а затем проверяет, что только пОсталась -1 буква. Это действительно однозначно, так как существует только один п-е последнее письмо.

Включение и связанные с ним проблемы

Три PSPACE -сложные задачи для общих NFA относятся к PTIME для DFA и сейчас рассматриваются.

Включение

За полиномиальное время разрешимо, является ли язык одного УФА подмножеством другого языка УФА.

Набросок доказательства включения

Позволять А и B быть двумя УФА. Позволять L(А) и L(B) быть языками, принятыми этими автоматами. потом L(А)⊆L(B) если и только если L(А∩B)=L(А), куда А∩B обозначает автомат декартова произведения, что также может быть доказано однозначно. Сейчас же, L(А∩B) является подмножеством L(А) по конструкции; следовательно, оба набора равны тогда и только тогда, когда для каждой длины п∈ℕ, количество слов длины п в L(А∩B) равно количеству слов длины п в L(А). Можно доказать, что достаточно проверить каждый п до произведения количества состояний А и B.

Количество слов длины п принятый автоматом может быть вычислен за полиномиальное время, используя динамическое программирование, что завершает доказательство.[1]

Связанные проблемы

Проблема универсальности[примечание 1] и эквивалентности,[заметка 2] также принадлежат PTIME, сведением к проблеме включения.

Проверка, однозначен ли автомат

Для недетерминированного конечного автомата А с п государства и м буква алфавита, разрешима во времени О (п2м) ли А однозначно.[2]

Набросок доказательства однозначности

Достаточно использовать алгоритм фиксированной точки для вычисления множества пар состояний q и q ' такое, что существует слово ш что приводит к q и чтобы q ' . Автомат однозначен тогда и только тогда, когда не существует такой пары, что оба состояния принимают. Есть не больше О(п2) пары состояний, и для каждой пары есть м буквы, которые необходимо рассмотреть, чтобы возобновить алгоритм фиксированной точки, отсюда и время вычисления.

Некоторые свойства

Сложность состояния

Основная статья: Сложность состояния

Математические доказательства того, что каждому UFA для языка требуется определенное количество состояний, были впервые представлены Шмидтом.[4] Leung доказал, что DFA эквивалентен -государственный УФА требует состояния в худшем случае. и UFA эквивалент -state NFA требует состояния.[5]

Йирасек, Йираскова и Шебей[6] исследовал количество состояний, необходимых для представления основных операций над языками. В частности, они доказали, что для каждого -государственный УФА, дополнение принятого языка принимается УФА с состояния.

Для однобуквенного алфавита Охотин доказал, что DFA эквивалентен -государственный УФА требует состояния в худшем случае.[7]

Примечания

  1. ^ то есть: учитывая UFA, принимает ли он каждую строку Σ*?
  2. ^ то есть: учитывая два UFA, принимают ли они один и тот же набор строк?

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

  • Кристоф Лёдинг, Однозначные конечные автоматы, Развитие теории языка, (2013) стр. 29–30 (Слайды )
  1. ^ Кристоф Лёдинг, Однозначные конечные автоматы, Слайд 8
  2. ^ Сакарович, Жак; Томас, Рувим. Элементы теории автоматов. Кембридж: издательство Кембриджского университета. п. 75. ISBN  978-0-521-84425-3.
  3. ^ Кристоф Лёдинг, Однозначные конечные автоматы, Слайд 8
  4. ^ Шмидт, Эрик М. (1978). Краткость описания контекстно-свободных, регулярных и однозначных языков (Кандидат наук.). Корнелл Университет.
  5. ^ Люнг, Хинг (2005). «Описательная сложность NFA разной неоднозначности». Международный журнал основ информатики. 16 (05): 975–984. Дои:10.1142 / S0129054105003418. ISSN  0129-0541.
  6. ^ Йирасек, Йозеф; Йираскова, Галина; Шебей, Юрай (2016). «Операции над однозначными конечными автоматами». 9840: 243–255. Дои:10.1007/978-3-662-53132-7_20. ISSN  0302-9743. Цитировать журнал требует | журнал = (помощь)
  7. ^ Охотин, Александр (2012). «Однозначные конечные автоматы над унарным алфавитом». Информация и вычисления. 212: 15–36. Дои:10.1016 / j.ic.2012.01.003. ISSN  0890-5401.