平成１９年　技術士第一次試験問題　Ⅳ

平成１９年度　技術士第一次試験問題【専門科目】

次の有限状態機械 (オートマトン) が受理するすべての文字列の集合として、最も適切なものを①～⑤の中から選べ。ただし、入力される文字列のアルファベットは {a, b} とし、図中の二重丸は終了状態を表すものとする。

　

①　aa という部分列が含まれない文字列の集合

②　abという部分列が含まれる文字列の集合

③　a と b が交互に現れる文字列の集合

④　a から始まり長さ3以上の文字列の集合

⑤　a が高々1個しか含まれない文字列の集合

①

選択肢の条件に合致する文字列であっても、受理しない文字列があればその選択肢は適切でないことになる。
また、問題に「有限状態機械が受理するすべての文字列の集合」と記載があるので、選択肢の条件に合わない文字列なのに受理する文字列があってもその選択肢は適切でないことになる。

①　正しい。aaが含まれると必ず受理されない。

②　abaa は条件に合致する文字列であるが、受理しない。

③　abba は受理するので誤り。

④　aab は条件に合致する文字列であるが、受理しない。

⑤　abab は、a が2個あるのに受理するので誤り。