オートマトン

現実逃避のためにオートマトンに関する基本的な演習問題をちょこちょこ解いていた orz
「アルファベットΣ={a}と固定したとき，任意のNFA Aについてそれが受理する言語L(A)がどんなものか説明せよ」という問には悩まされた．
もちろん完全な答えが書ける類の問題ではないのだが，任意のNFA Aを構成する系統だった方法があればL(A)の持つ性質もそこそこ厳密に議論できる．ということで任意のNFAを帰納的に（連接と合併とKleeneのスターとで）構成する手順を考えてみたのだが，そもそもbase caseをどうすればよいのやら．Base caseのNFAはいくつの状態数を持つべきか？ 受理状態はいくつ？ ε遷移は入る/入らない？ とか分からないことが多過ぎるので諦めた．以下，考えたこと

• アルファベットの元が1つしかないので文字列は「長さ」についての情報しか持たないのは自明で，その長さに関する制限がどうなるかを考えたい．
• 「オートマトンは記憶ができない」つまりループがあったらそこを何回まわろうと区別がない．単純なN状態のループだけを持つオートマトンでは，受理する文字列wは|w|=kNをみたす．このことを一般化できればいいんじゃないかな？
• 例えば3状態のループと5状態のループとを連接したら，3と5とは互いに素なので|w|は任意の自然数であってよい．
• 例えば3状態のループと5状態のループとの合併を取ったら，|w|=3k or 5kであってよい．
• ループの途中を受理状態にすれば|w|=kN+jであってよい．

そう言えば明日は情報理工学系研究科の院試だそうな．（地下方面の）いろんな人から「来年は一緒にCS専攻受けようね」って言われる...