次のようなBNFで定義された文法を考える。
<S> :: = <A><B>
<A> :: = a | a<A>
<B> :: = b | b<B> | c | c<B>
ここで、< > で囲まれたものは非終端記号、英小文字1文字は終端記号とし、開始記号を <S> とする。この文法により生成される文を正規表現で表したものはどれか。ただし、正規表現において
* は直前のものの0回以上の繰り返しを表す。| は選択を表すものとする。
① a*b*c
② a*(b | c)*
③ aa*(bb* | cc*)
④ aa*(bc)(bc)*
⑤ aa*(b | c)(b | c)*
⑤
① a*b*c* の正規表現では、例えば a が0回、すなわち a がなくてもよいが、BNFでは、
<S> :: = <A><B>
つまり、 (a | a<A>)<B>により、a が少なくとも1つ以上は現れなければならない。
② ①と同様であり、誤り。
③ BNFでは、例えば abc が表現可能であるが、正規表現では生成できない。
④ BNFでは、例えば abb や acc が表現可能であるが、正規表現では生成できない。
⑤ 正しい。
| Ⅲ－３ | 目次 | Ⅲ－５ |