令和7年度 III-1

解説

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

正規表現 (a*(ab)*|c)*ad* にマッチしない文字列を選ぶ問題。

解き方

① (a*(ab)*|c)*ad* は「a・b・cの並び」+「a」+「dの並び」。dは最後のadの後ろにしか出てこない
② dが途中にあり、その後にまた別の文字が続くものを探す。③aabcadadは1つ目のdの後ろにadが続く
③ ③

正解が正しい理由

正規表現は、「a*(ab)*」又は「c」を0回以上繰り返した後に、「a」と、0個以上の「d」が続く形である。繰り返しの中の要素には文字dが含まれないため、最後の「a」より前にdがあってはならず、dは末尾の「ad*」の部分にのみ現れる。③aabcadad は、aab(=a+ab)、c までは繰り返し部分で表せるが、その後の「ad」の後にさらに「ad」が続いており、最後の「a」より前にdが現れるため、この正規表現では表せない。したがって③が最も不適切である。

各選択肢について

• ① ccaaabaa は、c、c、aaab(a*=aa と ab)、a(a*)、末尾のa、と分解でき、表せる。
• ② cabaacad は、c、ab、aa(a*)、c、末尾のad と分解でき、表せる。
• ③ aabcadad は、繰り返し部分の途中の「ad」のdが、繰り返し要素(a*(ab)*またはc)では表せないため、表せない。これが正答(最も不適切)。
• ④ abcadddd は、ab、c、末尾のadddd と分解でき、表せる。
• ⑤ abcabcad は、ab、c、ab、c、末尾のad と分解でき、表せる。

覚えるべきポイント

正規表現では、*(0回以上の繰り返し)、|(選択)、連接に従って文字列を分解して確認する。この式では、dは末尾の ad* の部分でしか現れない。