Автомат Мюллера - Википедия - Muller automaton

В теория автоматов, а Автомат Мюллера это тип ω-автомат. Условие приемки отделяет автомат Мюллера от других ω-автоматов. Автомат Мюллера определяется с помощью условие приема, т.е. совокупность всех состояний, посещаемых бесконечно часто, должна быть элементом приемочного множества. И детерминированные, и недетерминированные автоматы Мюллера распознают ω-регулярные языки. Они названы в честь Дэвид Э. Мюллер, американец математик и специалист в области информатики, который изобрел их в 1963 году.^[1]

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

Формально детерминированный автомат Мюллера кортеж А = (Q, Σ, δ,q₀,F), который состоит из следующей информации:

• Q это конечный набор. Элементы Q называются состояния из А.
• Σ - конечное множество, называемое алфавит из А.
• δ:Q × Σ →Q это функция, называемая функция перехода из А.
• q₀ является элементом Q, называемое начальным состоянием.
• F представляет собой набор наборов состояний. Формально, F ⊆ п(Q) куда п(Q) является powerset из Q. F определяет условие приема. А принимает именно те прогоны, в которых множество бесконечно часто встречающихся состояний является элементомF

В недетерминированный автомат Мюллера, функция перехода δ заменяется отношением перехода Δ, которое возвращает набор состояний, а начальное состояние равно q₀ заменяется набором начальных состояний Q₀. Как правило, автомат Мюллера относится к недетерминированному автомату Мюллера.

Для более полного формализма посмотрите ω-автомат.

Эквивалентность другим ω-автоматам

Автоматы Мюллера одинаково выразительный в качестве автоматы четности, Автоматы Рабина, Уличные автоматы, и недетерминированный Büchi автоматы, чтобы упомянуть некоторые, и строго более выразительные, чем детерминированные автоматы Бюхи. Эквивалентность вышеупомянутых автоматов и недетерминированных автоматов Мюллера может быть продемонстрирована очень легко, поскольку условия приема этих автоматов могут быть эмулированы с использованием условия приема автоматов Мюллера. Теорема Макнотона демонстрирует эквивалентность недетерминированного автомата Бюхи и детерминированного автомата Мюллера. Таким образом, детерминированный и недетерминированный автомат Мюллера эквивалентны в терминах языков, которые они могут принимать.

Преобразование к недетерминированному автомату Мюллера

Ниже приводится список конструкции автоматов который переводит тип ω-автоматов в недетерминированный автомат Мюллера.

Из Büchi автомат

Если ${ displaystyle B}$ - множество конечных состояний в автомате Бюхи с множеством состояний ${ displaystyle Q}$, мы можем построить автомат Мюллера с тем же набором состояний, переходной функцией и начальным состоянием с условием принятия Мюллера как F = {X | X ∈ 2^Q ∧ X ∩ B ≠ ${ displaystyle emptyset}$}

Из автомата Рабина / Автомат четности

Аналогично условия Рабина ${ displaystyle (E_ {j}, F_ {j})}$ можно смоделировать, построив набор приемки в автоматах Мюллера, поскольку все наборы в ${ Displaystyle F substeq 2 ^ {Q}}$ которые удовлетворяют ${ Displaystyle F cap E_ {j} = emptyset land F cap F_ {j} neq emptyset}$, для некоторых j. Обратите внимание, что это также относится и к случаю автомата контроля четности, поскольку условие принятия четности может быть легко выражено как условие принятия Рабина.

Из автомата Streett

Условия Streett ${ displaystyle (E_ {j}, F_ {j})}$ можно смоделировать, построив набор приемки в автоматах Мюллера, поскольку все наборы в ${ Displaystyle F substeq 2 ^ {Q}}$ которые удовлетворяют ${ Displaystyle F cap E_ {j} = emptyset rightarrow F cap F_ {j} = emptyset}$, для всех j.

Преобразование к детерминированному автомату Мюллера

Объединение двух детерминированных автоматов Мюллера

От Büchi automaton

Теорема Макнотона предоставляет процедуру преобразования недетерминированного автомата Бюхи в детерминированный автомат Мюллера.

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

• Автоматы на бесконечных словах Слайды к учебнику Паритоша К. Пандьи.
• Иде Венема (2008) Лекции по модальному μ-исчислению; в Версия 2006 г. был представлен на 18-й Европейской летней школе по логике, языку и информации