平成21年 春期 応用情報技術者 午前 問3

次に示す有限オートマトンが受理する入力例はどれか。
ここで、S1は初期状態を、S3は受理状態を表している。

 ア  1011  イ  1100  ウ  1101  エ  1110


答え ウ


解説
選択肢の入力を行ったときの動作を確認する。

 ア  1011を入力すると、S1−(1)→S2−(0)→S2−(1)→S1−(1)→S2になり、受理しない。
 イ  1100を入力すると、S1−(1)→S2−(1)→S1−(0)→S3−(0)→S2になり、受理しない。
 ウ  1101を入力すると、S1−(1)→S2−(1)→S1−(0)→S3−(1)→S3になり、受理する。
 エ  1110を入力すると、S1−(1)→S2−(1)→S1−(1)→S2−(0)→S2になり、受理しない。


キーワード
・有限オートマトン

キーワードの解説
  • 有限オートマトン
    有限個の状態(○)と遷移の組合せで、動作(ふるまい)を表現したもの
    状態(○)と状態(○)の矢印(→)は状態の遷移を表し、矢印(→)の添え字は矢印の遷移を行うときのデータの条件を表します。
    有限オートマトンは、入力されたデータをシステムが処理可能かを判断するのに使用します。(文章で書くとあいまいになりがちな仕様を明確にするために使用します。)

もっと、「有限オートマトン」について調べてみよう。

戻る 一覧へ 次へ