オートマトンと形式言語（オフィスアワー）

先生が遅れてしまったので、演習ではなく、補講。午前中の逆の命題「決定性オートマトンで定義される言語はある正則表現で表すことができる」という定理の証明。決定性オートマトンと非決定性オートマトンは相互に変換が可能なので*1、逆の命題になる。これは結構複雑。というのも記号がかなりたくさん出てくるからで、復習が必要だ。

*1:正確には非決定性オートマトンは決定性オートマトンの一つでもある