Question

ナナ

情報系、オートマトンについてわかる人がいたら教えてください。
わからないのはこの問題です。

なぜこの答えになるかかいせつが欲しいです

問1.10 進数を表す記号列を受理する有限オートマトン
次の条件の10進数を表す記号列を受理する有限オートマトンを考える.
+ または の符号が付く (符号は付かなくとも良いとする)
整数部は0から9までの数字の列で構成される
小数点が付く
小数部は0から9までの数字の列で構成される
ただし, 整数部または小数部は, 空列でも良いが, 少なくとも一方は空でないとする.
上記の条件を満たす次のNFAM = (Q,2,8,90,F) が与えられたとする. ここで, 2=
{0,1,..., 9,.,+,-}である.
90
.+..
0,1,..., 9
91
0,1,..., 9
92
94
10.1.
0,1,..., 9
9.
193
95
NFA M が 10 進数を表す記号列を受理することを説明しなさい. 説明にあたっては具体
例を用いて構わない. ただし, 10進数の条件である 「符号｣ 「整数部」 「小数点」 および 「小
数部」 について言及すること.
以上

オートマトン

Answer 1

Dylan🍔

有名な書籍の例題そのまま？
ホップクロフト著のオートマトン本（サイエンス社）の１冊目
有限オートマトンの部分に書かれていると思います。
手元になければ、大学か自治体の図書館で。

ナナ

コメントありがとうございます。
この本で合ってますか？

Dylan🍔

その本の有限オートマトンの章、
ε を含むものの項に、例として同じ図がありませんか？
その説明を見れば回答できそうな気がします。

Dylan🍔

簡単なオートマトンを理解できていますか？
εのないものは分かりますか？
正規表現という言葉はすでに習っていますか？

Dylan🍔

わかりやすくするために、
状態遷移を少しシンプルにしてみましょう。

まず、εを消します。
q5に遷移するものがないので、q5を消します。
代わりに、q3を受理状態とします。
q1, q3 の自分自身への遷移も消してみます。
これでかなりシンプルになりました。

このオートマトンは何を受理しますか？

Dylan🍔

この簡単なものがわかったら、
ε と q5 を元に戻して（復活させて）みます。
受理状態は q5 にします。

このオートマトンは何を受理しますか？

Dylan🍔

先ほどのオートマトンがわかれば、
q1, q3 の自分への遷移も元に戻して、
最初の問題のオートマトンで考えましょう。
受理するものがわかると思います。

Dylan🍔

どうしてもわからなければ、
問題の「上記の〜」より上の部分だけを見て、
自分でオートマトンを構成してみてください。
このプリントにあるものとは
別の形になっても構いません。

実は、正解は他にもあります。