Автомат Мюллера
-
Определение и свойства автомата Мюллера
- Автомат Мюллера является разновидностью ω-автомата, отличаясь условием принятия.
- Набор состояний, посещаемых бесконечно часто, должен быть элементом условия принятия.
- Детерминированные и недетерминированные автоматы Мюллера распознают ω-регулярные языки.
- Дэвид Э. Мюллер, американский математик, изобрел автоматы Мюллера в 1963 году.
-
Формальное определение автомата Мюллера
- Детерминированный автомат Мюллера состоит из конечного множества состояний, алфавита, переходной функции, начального состояния и условия принятия.
- Недетерминированный автомат Мюллера отличается функцией перехода и начальным состоянием.
- Обычно термин «автомат Мюллера» относится к недетерминированному варианту.
-
Эквивалентность с другими ω-автоматами
- Автоматы Мюллера эквивалентны автоматам четности, Рабина, Стритта и Бюхи.
- Условия принятия автоматов Мюллера могут быть эмулированы условиями принятия других автоматов.
- Теорема Макнотона доказывает эквивалентность детерминированных и недетерминированных автоматов Мюллера с точки зрения принимаемых языков.
-
Преобразование к недетерминированным автоматам Мюллера
- Существуют процедуры преобразования различных типов ω-автоматов в автоматы Мюллера.
-
Рекомендации
- Ссылки на учебные пособия и лекции по модальному μ-исчислению.