• はてなアカウントでログイン
• 無料ユーザー登録

ベストアンサー

• pmint2015/09/22 14:46:18

  満足70pt

  表記順序が分かりにくいんだと思います。
  
  簡略化して

  R0 ::= 3
  A  ::= R0｜A R0
  

  これだとAからは3、33、333…が生成可能です。
  
  次に

  R0 ::= 3
  R1 ::= 1
  A  ::= R0｜A R0｜B R0
  B  ::= R1
  

  これならAからは3、3 3、3 3 3…のほか、1 3も生成可能になります。（Bからは1のみ生成可能）
  
  続くほど左に数字が増えていく定義になっています。
  また、再帰的に続く場合と、終端（左端の文字）が一緒くたに定義されているため、より分かりにくくなっています。
  
  
  2つのリンク先ではどちらも<R0> <R1> <R2>に置き換えて統一することで、考えやすくしているようです。
  
  これを踏まえて、2番目のリンク先を補足するとこんな感じでしょうか。
  

  （解説1、2、3は省略）
  
  4. ここまでで1 2という文字列に該当するのは<A>のみです。そして<A>はBNFにある通り、<B><R2>と置換可能です。
  
  5. 問題文より<A>から生成できる文字列さえ考えればいいのですが、
  非終端記号である<A>から1 2を生成する例は…
  <A>
  = <A><R0> （BNFより。以下も同様）
  = <B><R2><R0> （<A>部分を解説4に基づいて置き換えた結果）
  = <R1><R2><R0> （<B>を分かりやすく置換）
  …しか該当しません。
  これが<A>から生成可能で、左端が1 2で「終わる」例を探した結果です。
  
  5.5. ここで、1番目のリンク先にある解説から <R1><R2><R0> を探してみてください。
  
  6. [ア]の123だけが生成可能だと分かります。
  

  スター

  • 

    1件のコメントを見る

  • kon39392 2015/09/22 17:39:24

    ありとうございます。
    どの回答もわかりやすかったですが、理解力のない私がピンとくるきっかけを与えてくださったのでベストアンサーとさせてください。
    
    ありがとうございました。

    スター

その他の回答

• Mook2015/09/22 13:04:42

  満足65pt

  二つの回答は攻める方向が逆ですが、どちらでやるのがやりやすいか、ご自身で確認して見てください。

  解説の二番煎じですが、下の方の回答（元の数字から<A> に辿っていく）の方法で考えてみると、
  
  回答群のすべてが12# で、最初の二つの数字はすでに確定していますから、
  この始めの二桁の形は
  
  <R1> <R2>
  です。<R1>は終端<B>なので
  
  <B> <R2>  =>  <A>
  の形です。
  
  初めの２桁が<A>の三桁の数値を生成するのは
  <A> <R0>  =>  <A>
  <A> <R1>  =>  <B>
  <A> <R2>  =>  <C>
  ですが、<A> から生成されるのですから、
  
  <A> ::= <A> <R0>
  の形で、最終桁は<R0> とわかります。回答群の中で、末尾が R0 に含まれるのは 3 だけなので
  回答は [ア] になります。
  
  上の回答は<A> から数字に分解して一致するかを確認しているので、考える方向が逆になっていますが
  どちらでも回答は一緒になります。
  

  スター

jan82015/09/22 13:47:26

満足65pt

ちょっと複雑なだけですよ

例えばBNFの規則に従って、
<A>::=<R0>⇒6
<B>::=<R1>⇒7
<C>::=<R2>⇒8
<A>::=<A><R0>⇒63
<B>::=<A><R1>⇒637
<C>::=<B><R1>⇒6374
<B>::=<C><R2>⇒63748
<A>::=<B><R2>⇒637488
<A>::=<A><R0>⇒6374883
などと、文字列をずーっと生成する事が出来ます。
これは、
<A>
=<A><R0>
=<B><R2><R0>
=<C><R2><R2><R0>
=<B><R1><R2><R2><R0>
=<A><R1><R1><R2><R2><R0>
=<A><R0><R1><R1><R2><R2><R0>
=<R0><R0><R1><R1><R2><R2><R0>
=6374883
と表す事が出来ます。

問題文は「<A>は123,124,127,128の内どれか？」と聞いています。
123,124,127,128を<A>から生成しようとすると、
<B>::=<R1>⇒1
<A>::=<B><R2>⇒12
<A>::=<A><R0>⇒120 または 123 または 126 または 129
となるので、<A>になるのは123しかありません。

「4．ここまでの12に該当するのは<A>=<B><R2>のみです。」の解説
<A><B><C>のBNF記法をよく見ると、ほとんどが2文字の組み合わせになっており、1文字単独で構成できるのは、
<A>::=<R0>
<B>::=<R1>
<C>::=<R2>
の3つしかありません。
従って、1は、<B>=<R1>しかありません。
続いて、12は、<A>::=<B><R2>=<R1><R2>しかありません。

スター
• その他の回答を読む

この質問へのコメント

質問の情報

登録日時

2015-09-22 11:52:25

終了日時

2015-09-22 17:40:45

回答条件

1人3回まで

この質問のカテゴリ

• コンピュータ
• 学習・教育

この質問に含まれるキーワード

人気の質問

• 不満なことを周りに当たり散らして会社で浮いた存在になるのと、辛抱して鬱病になるのは、どちらがマシで…coccinellab211日前
• 【今年の漢字】(2023年)を予想してみてください。 ※遠慮なく気軽にどうぞ。(^_^; ※参考URL http://www.ka…rsc2215時間前
• ビジネスで部下を指導されてる方や学校の先生、塾の先生などにご意見いただければ幸いです。 私はIT系の仕…匿名質問者1112日前
• エアコンの専用ブレーカがたまに落ちます エアコン本体の過電流による原因ではない気がします。 エアコン…coccinellab11日前
• iMacの作業中なぜか デスクトップにあるファイル（開いた外部ハードディスクのファイルも）が突然すべてが…iquestion111日前

メニュー

• 質問一覧
• カテゴリ一覧
• 無料ユーザー登録
• 人力検索はてなトップ

PC版

• お問い合わせ
• ヘルプ
• お知らせ
• はてなトップ