McNaughton’s theorem とは

オートマトンの理論では、McNaughtonの定理は、ω正規言語の集合が決定論的なミュラーオートマトンによって認識可能な言語の集合と同一であると主張する定理を指す。この定理は、任意のω規則言語のための決定論的なミュラーオートマトンを構築するアルゴリズムを供給することによって証明され、その逆もまた同様である。
この定理には多くの重要な結果があります。 Büchiオートマトンとω-レギュラー言語は等しく表現されているため、BüchiオートマトンとMutlerオートマトンは等しく表現されています。確定的なMullerオートマトンの補完は簡単なので、Büchiオートマトン/ω正規言語は補完的に閉じられることを意味する。