技術士試験ナビ

技術士試験対策・テキスト・過去問題解説を発信します。

技術士第一次試験専門科目 平成28年度 Ⅲ-4

 次のようなBNFで定義された文法を考える。
  <S> :: = <A><B>
  <Α> :: = 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> :: = a | a<A> は,aが1回以上連続
<B> :: = b | b<B> | c | c<B> は,bかcが1回以上連続することを意味します。
ここで<B>は,bとcどちらか一方の連続に限らず,交互(例えば,bccbc)の連続も含まれることに注意が必要です。
よって,<S> :: = <A><B> は,「aが1回以上連続した後,bかcが1回以上連続(bとcは交互でも可)する」ことになります。

① a*b*c*
a*は,aが0回ということもあり得るため,不適切です。

② a*(b|c)*
a*は,aが0回ということもあり得るため,不適切です。

③ aa*(bb*|cc*)
bb*|cc*は,bかcの連続しか表現できないため,不適切です。

④ aa*(bc) (bc)*
(bc)*は,bとc交互の連続しか表現できないため,不適切です。

⑤ aa*(b|c)(b|c)*
適切です。