人間の言葉をそのまま理解できないコンピュータには、コンピュータが理解できる言語を使う必要があります。このように、コンピュータにはコンピュータならではの理論があり、ここではそんな情報（コンピュータ）に関する理論をいくつか紹介します。
1.オートマトン
オートマトンとは、状態遷移図のモデルです。
たとえばタスク管理において、「実行状態」「実行可能状態」「待ち状態」の3つの状態を遷移します。
過去問（H20FE秋午前問29）では、コンピュータのタスクの状態遷移として、次の図が記載されています。
また、実行状態のタスクが、「自分より優先度の高いタスクが実行可能状態になった」ことで、実行可能状態に遷移するともあります。
このように、ある「状態」と「遷移」の様子を表したモデルがオートマトンです。かつ、状態や遷移が有限なものが有限オートマントンです。
実際の過去問（H21春AP午前問3）の有限オートマトンを見てみましょう。問題文には、「S1は初期状態を,S3は受理状態を表している。」とも記載があります。
ここで、初期状態のS1に1が与えられるとS2に遷移し、0が与えられるとS3に遷移します。
S2においては、0が与えられるとS2のままで、1が与えられるとS1に遷移します。
S3においては、0が与えられるとS2に遷移し、1が与えられるとS3のままです。
2.オートマトンの過去問
（１）H28秋AP午前問4
問4 表は，入力記号の集合が{0, 1},状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。 ア a イ b ウ c エ d |
さて、よくわからない問題だと感じた人も多かったことでしょう。状態集合が{a, b, c, d}であり、それに対して入力記号の集合が{0, 1}です。問題文の状態遷移表をオートマトンの図にすると、以下になります。
ここで、最後が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ですからウです。
（２）H26春AP問4
問4 表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。
ア a イ b ウ c エ d
【正解】ウ
（３）H25春AP問3
問3 図は，偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。 a，bの適切な組合せはどれか。
↓
↓
↓
【正解】ウ
コメント