応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

オートマトン

人間の言葉をそのまま理解できないコンピュータには、コンピュータが理解できる言語を使う必要があります。このように、コンピュータにはコンピュータならではの理論があり、ここではそんな情報(コンピュータ)に関する理論をいくつか紹介します。

 

1.オートマトン

オートマトンとは、状態遷移図のモデルです。
たとえばタスク管理において、「実行状態」「実行可能状態」「待ち状態」の3つの状態を遷移します。
過去問(H20FE秋午前問29)では、コンピュータのタスクの状態遷移として、次の図が記載されています。
状態遷移
また、実行状態のタスクが、「自分より優先度の高いタスクが実行可能状態になった」ことで、実行可能状態に遷移するともあります。

このように、ある「状態」と「遷移」の様子を表したモデルがオートマトンです。かつ、状態や遷移が有限なものが有限オートマントンです。

実際の過去問(H21春AP午前問3)の有限オートマトンを見てみましょう。問題文には、「S1は初期状態を,S3は受理状態を表している。」とも記載があります。
automaton
ここで、初期状態のS1に1が与えられるとS2に遷移し、0が与えられるとS3に遷移します。
S2においては、0が与えられるとS2のままで、1が与えられるとS1に遷移します。
S3においては、0が与えられるとS2に遷移し、1が与えられるとS3のままです。

2.オートマトンの過去問

(1)H28秋AP午前問4

問4 表は,入力記号の集合が{0,   1},状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。
manton
ア a   イ b   ウ c   エ d

さて、よくわからない問題だと感じた人も多かったことでしょう。状態集合が{a, b, c, d}であり、それに対して入力記号の集合が{0,   1}です。問題文の状態遷移表をオートマトンの図にすると、以下になります。
auto 
ここで、最後が110で終わっているものを受理すると、樹里状態はa~dのどれになるのでしょうか。というのが問題です。最後が110というのがよく分かりませんが、とにかく、a~dの4つの中のいずれかからスタートしますので、順番に入れてみます。

・aからスタート
 a→1→b→1→d→0→c
・bからスタート
 b→1→d→1→d→0→c
・cからスタート
 c→1→b→1→d→0→c
・dからスタート
 d→1→d→1→d→0→c

このように、どこからスタートしても110を受理すると、cで受理状態になります。
正解は、cですからウです。

(2)H26春AP問4
問4 表は,入力記号の集合が{0,1},状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。
H26h-4
ア a   イ b   ウ c   エ d
【正解】ウ

(3)H25春AP問3
問3 図は,偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり,二重丸が受理状態を表す。 a,bの適切な組合せはどれか。
H25h-3_1図H25h-3_2選択肢表


【正解】ウ