アルファベット {a, b} 上の正規表現のうち、(a|b)* と同じ言語を表すものはどれか。

解説

正解は「(a*b*)*」です。(a|b)* は、a と b からなるすべての文字列（空列を含む）を表します。a*b* は a の並びの後に b の並びが続く形で、これを0回以上繰り返すと、a と b を任意の順に並べた文字列を作れます。例えば ba は、1回目で b（a を0個、b を1個）、2回目で a を選べば得られます。「a*b*」は、b の後に a が来る ba のような文字列を表せません。「(ab)*」は ab の繰返しだけで、aa なども表せません。「a*|b*」は a だけ、または b だけの文字列で、ab のように両方を含む文字列を表せません。