平成25年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
V−6
下図の有限オートマトンが受理するすべての文字列の集合として、最も適切なものは
どれか。ただし、入力される文字列のアルファベットは {a, b} とし、図中の二重丸は
終了状態を表すものとする。

 

 @ aが3つ以上連続する文字列の集合
 A aaという部分列が含まれる文字列の集合
 B bが2つ以上連続することはない文字列の集合
 C bが高々1回しか含まれない文字列の集合
 D bbaaという文字列が繰り返し現れる文字列の集合




【正解】 A

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

図の有限オートマトンにについて、
図中の大きな ○ を初期状態から (左端から) 順に X、Y、Zとする。

初期状態Xで
が入力されるとYに遷移する。
初期状態Xで
が入力されるとXの状態のままである。
いずれにしても、◎の終了状態ではないため、文字列
は受理しない。

初期状態でaaが入力されるとXYZの順に遷移するため受理する。

@ 
aaは3つ以上連続する文字列ではないが、受理するので誤り。
A 正しい。
B 
aaはbが2つ以上連続していないのに受理するので誤り。
C 
baabaabbは受理するので誤り。
D 
bbaabは、bbaaという文字列が繰り返し現れていないのに
 受理するので誤り。

EXCELのマクロのご相談なら ファーストマクロ 



V−5 目次 V−7
ファーストマクロ TOPページ