平成２５年度 技術士第一次試験問題【専門科目】
Ⅲ－６
下図の有限オートマトンが受理するすべての文字列の集合として、最も適切なものはどれか。ただし、入力される文字列のアルファベットは {a, b｝とし、図中の二重丸は終了状態を表すものとする。
① aが3つ以上連続する文字列の集合
② aaという部分列が含まれる文字列の集合
③ bが2つ以上連続することはない文字列の集合
④ bが高々1回しか含まれない文字列の集合
⑤ bbaaという文字列が繰り返し現れる文字列の集合
正解
②
解説
選択肢の条件に合致しても、受理しない文字列があればその選択肢は適切でないことになる。
また、問題に「有限オートマトンが受理するすべての文字列の集合」と記載があるので、選択肢の条件に合わないのに受理する文字列があってもその選択肢は適切でないことになる。
図の有限オートマトンにについて、図中の大きな ○ を初期状態から (左端から) 順に Ｘ、Ｙ、Ｚとすると以下のようなことが読み取れる。
・初期状態Ｘでaが入力されるとＹに遷移する。
・初期状態Ｘでbが入力されるとＸの状態のままである。
・初期状態でaaが入力されるとＸＹＺの順に遷移するため受理する。
これらを踏まえる。
① aaは3つ以上連続する文字列ではないが、受理するので誤り。
② 正しい。
③ aaはbが2つ以上連続していないのに受理するので誤り。
④ baabやaabbは受理するので誤り。
⑤ bbaabは、bbaaという文字列が繰り返し現れていないのに受理するので誤り。
| Ⅲ－５ | 目次 | Ⅲ－７ |