Os autômatos de Muller são igualmente expressivos como automatosautômatos de paridade, autômatos de Rabin, autômatos de Streett e autômatos de Büchi não determinísticos, para mensionarmencionar alguns, e estritamente mais expressivos que os autômatos de Büchi determinísticos. A equivalência do autômato acima e do autômato de Muller não determinístico pode ser visto muito facilmente como as condições de aceitação desses autômatos poderem ser simulados usando a condição de aceitação dos autômatos de Muller. O teorema de McNaughton's demonstra a equivalência do autômato de Büchi não determinísticos com o autômato de Muller determinístico. Assim, autômatos de Muller determinísticos e não determinísticos são equivalentes em termos das linguagens que eles aceitam.
==Transformação para um autômato de Muller não determinísticos==
