オートマトン理論再考

摘要

Automata are the simplest mathematical model of computation, so simple that they take forms in various diverse areas. In this survey, we present several theorems, one of which gives a new viewpoint for the classical theory of automata, and one of which shows a deep relation between formal language theory and other mathematical fields.%オートマトンは最も単純な計算のモデルである.その単純さゆえに初学者にとっても理解しやすく，情報系の学 部においては「計算理論」や「形式言語理論」などの講義はまずオートマトンから教え始めることが標準となってい る.一方，その単純さゆえに理論的な深みやさらなる研究の余地がないと誤解されることもしばしばあり，また，講 義や解説書においても応用的な需要からかより強力な計算モデルに重きが置かれることも多い.本サーベイではオートマトン理論の基礎から始め.三話構成でオートマトン·形式言語理論の様々な定理を解説 していく.解説する定理の中には.オートマトン理論における古典的な結果に別の視点を新たに与えるものもあれ ば，オートマトン·形式言語理論と関わりのなさそうな分野との意外な繋がりを見せるものもある.オートマトン理 論に習熟している方にも楽しんでもらぇるよう，最近の結果や話題についても内容に盛り込んだ.