令和元年度 III-1

解説

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

BNFで定義された文法が生成する文字列を、正規表現で表したものを選ぶ問題。

解き方

① <A>=aが1個以上 → aa*。<B>=bかcが1個以上で、bとcは混ぜてよい → (b|c)(b|c)*
② つなげて aa*(b|c)(b|c)*。①はbとcを混ぜられない、②はbcの組しか作れない、④⑤はaが0個やbcが0個も許してしまう
③ ③

正解が正しい理由

<A>::=a|a<A>はaの1回以上の繰り返しで、aa*と表せる。<B>::=b|b<B>|c|c<B>は、bまたはcを1回以上並べたもの(bとcは任意の順序で混在してよい)で、(b|c)(b|c)*と表せる。<S>::=<A><B>なので、全体はaa*(b|c)(b|c)*となる。したがって③が正しい。

各選択肢について

• ① bb*|cc*では、bだけ又はcだけの並びしか表せず、bcbのようにbとcが混在する文を表せない。
• ② (bc)(bc)*では、bとcが必ず交互に対で現れる文しか表せない。
• ③ aの1回以上の繰り返しの後に、bかcの1回以上の並びが続く。これが正答。
• ④ a*b*c*では、aが0個の文や、b・cが0個の文も含んでしまい、またcの後にbが来る文を表せない。
• ⑤ a*(b|c)*では、aやb・cが0個の文も含んでしまう。

覚えるべきポイント

X::=x|x<X>は「xの1回以上の繰り返し」=xx*。選択肢の違いは「0回を許すか(*)」「要素を混在できるか(b|c)」で見分ける。