En la teoría de los autómatas , un autómata de Muller es un tipo de autómata ω . La condición de aceptación separa a un autómata Muller de otros automa-autómatas. El autómata de Muller se define utilizando la condición de aceptación de Muller , es decir, el conjunto de todos los estados visitados infinitamente a menudo debe ser un elemento del conjunto de aceptación. Tanto los autómatas de Muller deterministas como los no deterministas reconocen los lenguajes regulares ω . Llevan el nombre de David E. Muller , un matemático e informático estadounidense , que los inventó en 1963. [1]
Definicion formal
Formalmente, un autómata de Muller determinista es una tupla A = ( Q , Σ, δ, q 0 , F ) que consta de la siguiente información:
- Q es un conjunto finito . Los elementos de Q se llaman los estados de A .
- Σ es un conjunto finito llamado el alfabeto de la A .
- δ: Q × Σ → Q es una función, llamada función de transición de A .
- q 0 es un elemento de Q , llamado estado inicial.
- F es un conjunto de conjuntos de estados. Formalmente, F ⊆ P ( Q ) donde P ( Q ) es powerset de Q . F define la condición de aceptación . A acepta exactamente aquellas corridas en las que el conjunto de estados que ocurren con una frecuencia infinita es un elemento de F
En un autómata Muller no determinista , la función de transición δ se reemplaza con una relación de transición Δ que devuelve un conjunto de estados y el estado inicial es q 0 se reemplaza por un conjunto de estados iniciales Q 0 . Generalmente, el autómata de Muller se refiere al autómata de Muller no determinista.
Para un formalismo más completo, mire ω-autómata .
Equivalencia con otros ω-autómatas
Los autómatas Muller son igualmente expresivos como los autómatas de paridad , los autómatas Rabin , los autómatas Streett y los autómatas Büchi no deterministas , por mencionar algunos, y estrictamente más expresivos que los autómatas Büchi deterministas. La equivalencia de los autómatas anteriores y los autómatas Muller no deterministas se puede mostrar muy fácilmente ya que las condiciones de aceptación de estos autómatas se pueden emular utilizando la condición de aceptación de los autómatas Muller. El teorema de McNaughton demuestra la equivalencia del autómata de Büchi no determinista y el autómata de Muller determinista. Por lo tanto, los autómatas de Muller deterministas y no deterministas son equivalentes en términos de los lenguajes que pueden aceptar.
Transformación en autómata Muller no determinista
A continuación se muestra una lista de construcciones de autómatas que transforman un tipo de ω-autómatas en un autómata Muller no determinista.
- Del autómata Büchi
- Si es el conjunto de estados finales en un autómata Büchi con el conjunto de estados , podemos construir un autómata de Muller con el mismo conjunto de estados, función de transición y estado inicial con la condición de aceptación de Muller como F = {X | X ∈ 2 Q ∧ X ∩ B ≠ }
- Del autómata de Rabin / autómata de paridad
- Del mismo modo, las condiciones de Rabin se puede emular construyendo el conjunto de aceptación en los autómatas Muller como todos los conjuntos en que satisfacen , para algunos j. Tenga en cuenta que esto también cubre el caso del autómata de paridad, ya que la condición de aceptación de paridad se puede expresar fácilmente como condición de aceptación de Rabin.
- Del autómata de Streett
- Las condiciones de Streett se puede emular construyendo el conjunto de aceptación en los autómatas Muller como todos los conjuntos en que satisfacen , para todos j.
Transformación en autómata muller determinista
- Unión de dos autómatas muller deterministas
- Del autómata Büchi
El teorema de McNaughton proporciona un procedimiento para transformar un autómata de Büchi no determinista en un autómata de Muller determinista.
Referencias
- ^ Muller, David E. (1963). "Secuencias infinitas y máquinas finitas". Cuarto Simposio Anual sobre Teoría de Circuitos de Conmutación y Diseño Lógico (SWCT) : 3–16.
- Autómatas en diapositivas de palabras infinitas para un tutorial de Paritosh K. Pandya.
- Yde Venema (2008) Conferencias sobre el cálculo μ modal ; la versión de 2006 se presentó en la 18a Escuela Europea de Verano en Lógica, Lenguaje e Información