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

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

Формальное определение [ править ]

Формально детерминированный Мюллер-автомат это набор A = ( Q ,Σ,δ, q0 _, — F ), который состоит из следующей информации:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки [ править ]

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

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

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

[1]