平成24年度 春期 午前 問3

✓ これが正解ウAGC

解説

三文字で一組なので長さが三の倍数になります。

設問が示す BNF の定義は、下の行から読むと形が見えます。いちばん下の行は、一文字が取り得る四種類を並べたものです。その上の行は、その一文字を三つ続けたものを一つの単位と定めています。いちばん上の行は、単位が一つ、あるいは定義そのものの後ろにもう一つ単位を足した形、という書き方で、単位を何個でも連ねられることを表しています。つまり合致する文字列の条件は二つだけです。使える四種類の文字だけでできていること、そして長さが三の倍数であることです。並んでいる文字列はいずれも四種類の文字だけでできていますので、条件の一方はすべてが満たします。そこで残るのは長さの条件だけになり、文字数が三のものが合致します。形式言語の定義を読む問では、このように測れる性質へ落としてから当てるのが速い進め方です。

ほかの選択肢はなぜ違うのか

• アAC：文字は使える四種類の中に収まっていますが、長さが二文字です。一つの単位は三文字と定められていますので、単位を一つも作れず、定義に合致しません。
• イACGCG：五文字あり、三文字の単位では割り切れません。単位を一つ作ると二文字余りますので、単位を連ねた形として読み切れず、定義から外れます。
• エATGC：四文字で、三文字の単位を一つ作ると一文字余ります。使える文字だけでできていても、余りが出る長さは単位の並びとして組み立てられません。