平成30年度 III-5

解説

この問題で問われていること

正規表現が表す言語の構造(先頭部分は、a、ab、cの繰返し、末尾は a と d の0回以上の繰返し)を理解して、文字列が一致するかを判定する問題。

解き方

① 形を読む: (a*(ab)*|c)* は a・b・c だけの部分、その後に a、最後に d* → d は末尾にしか出てこない
② ④ abacadad は途中の d の後に a が来ていて、この形にならない。他は「a・b・cの部分+a+dの並び」に分けられる
③ ④

正解が正しい理由

正規表現は、(a*(ab)*|c)*、a、d*の連結である。前半の括弧の中は、a、ab、cで作られる文字列(dは含まない)で、末尾は、aの後にdが0回以上続く。したがって、文字列は、(a、b、cのみの部分)+a+d*の形でなければならず、dが途中に現れることはない。④のabacadadは、途中にdがあり(abaca|d|ad)、dより前の部分に、dの後に更に、a と d が続く形になっていて、この形に合わない。したがって④が最も不適切である。

各選択肢について

• ① aaccaaddは、aacca(前半)+a+dd と分けられ(前半のaa、c、c、aを、a*とcで生成)、一致する。
• ② aabcabadは、aabcaba(前半)+a+d と分けられ(aab=a+ab、c、ab、a)、一致する。
• ③ acababaddは、acabab(前半)+a+dd と分けられ、一致する。
• ④ 途中にdがあり、dより後ろにaが再び現れるため、形に合わない。不適切で、これが正答。
• ⑤ aaacaaabaaadは、aaacaaabaaa(前半)+a+d と分けられ、一致する。

覚えるべきポイント

正規表現の判定では、文字列を先頭から、各部分表現に対応づけて分割してみる。ここでは、d は最後の d* にしか現れないので、dの後にa やb が現れる文字列は、一致しない。