次のような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が1度現れなければならないが、a*b*c と定義すると a が1度も現れない表記ができる。
② ①と同様である。
③ 問題の定義では、abcの表現が可能であるが、aa*(bb*|cc*) は、abcの表現ができない。
④ 問題の定義では、abbの表現が可能であるが、aa*(bc)(bc)* は、abbの表現ができない。
⑤ 正しい。
| Ⅳ－３ | 目次 | Ⅳ－５ |