平成28年度 III-4

解説

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

BNFで定義された文法が表す言語を、正規表現に書き換える問題。

解き方

① 「X|X<A>」の形の再帰はXの1回以上のくり返し(XX*)。<S>::=<A><B>は、<A>の後に<B>を続けたもの
② <A>=aが1回以上=aa*、<B>=bかcが1回以上=(b|c)(b|c)*
③ aa*(b|c)(b|c)*(⑤)

正解が正しい理由

<A>::=a|a<A>は、aが1回以上続く文字列で、正規表現ではaa*(a+)。<B>::=b|b<B>|c|c<B>は、bまたはcが1回以上続く文字列で、(b|c)(b|c)*。<S>::=<A><B>は、これらの連接で、aa*(b|c)(b|c)*となる。したがって⑤が正しい。

この問題で必要な基礎

■ BNFの読み方
「<A> ::= a | a<A>」は、「<A>は『a』か『aの後に<A>』のどちらかである」という意味です(|は「または」)。右側に自分自身(<A>)が出てくるので、aの後にまた<A>を続けることができ、結果として「aが1個以上並んだもの」になります。<B>も同様に、bかcが1個以上並んだもの(bとcが混ざってもよい)です。

■ 正規表現との対応
「aが1個以上」は、aを1個書いた後に「0回以上の繰り返し」a*を続けて、aa*と表します。「bかcが1個以上」は、(b|c)(b|c)*です。

各選択肢について

• ① a*b*c*は、空文字列も含み、また、bの後にcを続ける順序が固定されるなど、文法が生成する文と一致しない。
• ② a*(b|c)*は、aが0回でもよく、bとcも0回でもよいため、少なくとも1つのaと、少なくとも1つのbまたはcが必要な文法と一致しない。
• ③ aa*(bb*|cc*)は、bだけの列か、cだけの列で、bとcが混在する文を生成できない。
• ④ aa*(bc)(bc)*は、bcの繰返しに限られ、他の並びを生成できない。
• ⑤ aa*(b|c)(b|c)*は、aが1回以上、その後にbまたはcが1回以上続く形で、文法と一致する。これが正答。

覚えるべきポイント

<A>::=a|a<A>は、a+(aの1回以上の繰返し)。<B>も同様に(b|c)+。X+はXX*と書ける。