以下のサイトで勉強していると、「正規表現(111+11111)*が表す言語を認識する有限オートマトンを描け」という問題がありました。

結論から言えば、以下のようなNFAになります(上記のサイトから引用していますが、よく見ると、q0を受理状態とするのを忘れています）。

しかし、解説がなかったので、書きます。

この問題には面白い整数問題が含まれています。

それは、「n,mを非負整数として、3n+5mによって表される整数を全て求めよ。」という問題です（過去に大阪大学の入試問題としても出題されているようです）。

なぜなら、3つの1または5つの1を次々に結合していく操作を考えるためです。

この問題の解答は以下の様になります。

・m = 0のとき、3nなので、x mod 3 = 0となるような任意の非負整数xを表せます。

・m = 1のとき、3(n+1)+2なので、x mod 3 = 2となるような任意の5以上の整数xを表せます。

・m = 2のとき、3(n+3)+1なので、x mod 3 = 1となるような任意の10以上の整数xを表せます。

よって、この問題の答えは、1, 2, 4, 7以外の全ての非負整数です。
（解答終わり）

元の問題を考えると、1が0回以上連続していて、かつ1, 11, 1111, 1111111以外の文字列を受理するようなNFAを描けばよいということになります。

すると、最初に貼った図のようなNFAになります。

誤り、誤字、脱字などあれば教えて頂けると幸いです。