автомат Мюллера

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

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

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

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

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

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

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

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

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

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

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

Из автоматов Бюхи

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

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

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

Из автоматов Стритта

Условия Стритта можно смоделировать, построив множество приемки в автомате Мюллера как все множества, удовлетворяющие , для всех j . ${\displaystyle (E_{j},F_{j})}$ ${\displaystyle F\subseteq Q}$ ${\displaystyle F\cap F_{j}=\emptyset \implies F\cap E_{j}=\emptyset }$

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

Из автомата Бюхи

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

Ссылки

1. Мюллер, Дэвид Э. (1963). «Бесконечные последовательности и конечные машины». 4-й ежегодный симпозиум по теории коммутационных схем и логическому проектированию (SWCT) : 3–16.

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