Automata construction とは

オートマトン理論では、オートマトン構築は、ある所望の性質を持つオートマトンの存在を証明するために重要な数学的手法である。非常に頻繁に、それは、入力として所望のプロパティを取り、プロパティとしてオートマトンを出力として生成するアルゴリズムとして提示される。
オートマトン理論の多くの困難な問題には、オートマトンの正しい構築を見出し、問題に答えることができます。たとえば、McNaughtonの定理の有名な構成は、非決定論的なBüchiオートマトンが常に決定論的なMullerオートマトンに変換できるかどうかという疑問に答えました。