状態遷移関係

---

◆　オートマトン 　オートマトンとは、入力に対してその時の状態で処理を判断し結果を出力するものだそうです。 　・・・といってもどういう風に使用されているのか分からなかったのですけど、 情報処理の試験では、オートマトンの状態遷移図として問題が出てきます。 　例として下の様な図が、オートマトンの図です。 　問題を解くのに知っておかないといけない事は、開始点は太い矢印から、そして「受理状態」（ここでは二重円）のところで終わらないと行けません。 例はたまたま開始点と受理状態の点が一緒になっています。 　問題によっては、受理できるビット列はどれか？　とか、遷移先の値を問われる時があります。 　今度は特殊かも知れませんが、遷移表からオートマトンの図を求める場合です。 　 ０ １ Ａ Ａ Ｂ Ｂ Ｃ Ｄ Ｃ Ａ Ｂ Ｄ Ｃ Ｄ 　解き方としては、状態Ａの時に０が来た場合はＡ自身に、１が来た場合はＢに遷移するという考え方で遷移図を作ります。 すると下の様になります。 　これも過去問題なのですが、長さ３ビット以上の任意のビット列を左から読み込んで、最後が 110 で終わっているものを受理するにはどの状態を受理状態にすればいいか？ という問題があります。つまり　xxxxx・・・110 というビット列のデータを読み込んだ場合、受理状態はどれかと言う事です。 　開始点もはっきりしていないのですが、とりあえずＡ〜Ｄの全てを開始点として、110 の順で遷移していくと、必ずＣで終わると言うのが分かります。 よって答えはＣです。 　（多分、特殊なパターンの問題だと思います。）

TOPページに戻る