Факторный автомат - Quotient automaton - Wikipedia

В Информатика, в частности в формальная теория языка, а факторный автомат можно получить из заданного недетерминированный конечный автомат присоединившись к некоторым из ее государств. Фактор признает надмножество данного автомата; в некоторых случаях обрабатывается Теорема Майхилла – Нероде, оба языка равны.

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

A (недетерминированный) конечный автомат это пятикратный А = ⟨Σ, S, s0, δ, Sж⟩, куда:

  • Σ это вход алфавит (конечный, непустой набор символов),
  • S конечное непустое множество состояний,
  • s0 начальное состояние, элемент S,
  • δ это состояние перехода связь: δS × Σ × S, и
  • Sж - набор конечных состояний, (возможно, пустое) подмножество S.[1][примечание 1]

А нить а1...апΣ* признан А если есть государства s1, ..., sпS такой, что ⟨sя-1,ая,sя⟩ ∈ δ за я=1,...,п, и sпSж. Набор всех строк, распознаваемых А называется язык признанный А; он обозначается как L(А).

Для отношение эквивалентности ≈ на съемочной площадке S из АГосударства, факторный автомат А/ = ⟨Σ, S/, [s0], δ/, Sж/⟩ Определяется[2]:5

  • входной алфавит Σ быть таким же, как у А,
  • набор состояний S/ быть набором всех классы эквивалентности государств из S,
  • начальное состояние [s0], являющийся классом эквивалентности АНачальное состояние,
  • отношение переходное состояние δ/ определяется δ/([s],а,[т]) если δ(s,а,т) для некоторых s ∈ [s] и т ∈ [т], и
  • набор конечных состояний Sж/ - множество всех классов эквивалентности конечных состояний из Sж.

Процесс вычисления А/ также называется факторинг А по ≈.

Пример

Частные примеры
Автомат
диаграмма
Признанный
язык
Является частным от
А кB кC к
А:Фактор-автомат a, b, c, d.gif1+10+100
B:Фактор-автомат a = b, c, d.gif1*+1*0+1*00a≈b
C:Фактор-автомат a = b, c = d.gif1*0*a≈b, c≈dc≈d
D:Фактор-автомат a = b = c = d.gif(0+1)*a≈b≈c≈da≈c≈da≈c

Например, автомат А показано в первой строке таблицы[заметка 2] формально определяется как

  • ΣА = {0,1},
  • SА = {a, b, c, d},
  • sА
    0
    = а,
  • δА = {⟨A, 1, b⟩, ⟨b, 0, c⟩, ⟨c, 0, d⟩} и
  • SА
    ж
    = {b, c, d}.

Он распознает конечный набор строк {1, 10, 100}; это множество также можно обозначить регулярное выражение "1+10+100".

Соотношение (≈) = {⟨a, a⟩, ⟨a, b⟩, ⟨b, a⟩, ⟨b, b⟩, ⟨c, c⟩, ⟨c, d⟩, ⟨d, c⟩, ⟨ d, d⟩}, более кратко обозначаемый как a≈b, c≈d, является отношением эквивалентности на множестве {a, b, c, d} автомата АСостояний. Построение частного А этим соотношением приводит к автомату C в третьей строке таблицы; это формально определяется

  • ΣC = {0,1},
  • SC = {a, c},[заметка 3]
  • sC
    0
    = а,
  • δC = {⟨A, 1, a⟩, ⟨a, 0, c⟩, ⟨c, 0, c⟩} и
  • SC
    ж
    = {a, c}.

Он распознает конечный набор всех строк, состоящих из произвольного количества единиц, за которыми следует произвольное количество нулей, то есть {ε, 1, 10, 100, 1000, ..., 11, 110, 1100, 11000, ..., 111, ...}; этот набор также можно обозначить регулярным выражением «1*0*". Неформально C можно думать о результате А путем приклеивания состояния a к состоянию b и приклеивания состояния c к состоянию d.

В таблице приведены еще несколько частных отношений, например B = А/a≈b, и D = C/a≈c.

Характеристики

  • Для каждого автомата А и каждое отношение эквивалентности ≈ на множестве его состояний, L(А/) является надмножеством (или равно) L(А).[2]:6
  • Для конечного автомата А над некоторым алфавитом Σ, отношение эквивалентности ≈ можно определить на Σ* к Иксу если ∀ zΣ*: xzL(А) ↔ yzL(А). Посредством Теорема Майхилла – Нероде, А/ - детерминированный автомат, распознающий тот же язык, что и А.[1]:65–66 Как следствие, частное А каждым уточнение of ≈ также распознает тот же язык, что и А.

Смотрите также

Примечания

  1. ^ Хопкрофт и Уллман (раздел 2.3, стр.20) используют несколько иное определение термина δ, а именно. как функция из S × Σ к набор мощности из S.
  2. ^ На схемах автоматов в таблице символы из входного алфавита и названия штатов окрашены в зеленый и красный, соответственно; конечные состояния изображены в виде двойных кружков.
  3. ^ Строго формально набор SC = {[a], [b], [c], [d]} = {[a], [c]} ". Скобки классов опущены для удобства чтения.

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

  1. ^ а б Джон Э. Хопкрофт; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления. Ридинг / МА: Эддисон-Уэсли. ISBN  0-201-02988-X.
  2. ^ а б Тристан ле Галль и Бертран Жаннет (март 2007 г.). Анализ взаимодействующих бесконечных конечных автоматов с использованием решетчатых автоматов (PDF) (Издание Интерн). Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) - Campus Universitaire de Beaulieu. ISSN  1166-8687.