BNF(バッカス)記法について

次のBNFで定義されるビット列Sであるものは、どれか。
<S>::=01|0<S>1

ア、000111
イ、010010
ウ、010101
エ、011111

正解：ア

このように<変数>は、左辺と同じ変数を右辺で用いることが出来ます。
0<S>1を考えるには、まず<S>が使われていない「01」を代入します。
すると「0011」です。と記載されています。

自力で調べたのですが、
BNF(バッカス)記法で書かれた問題が読めません。
何故「01」を代入すると「0011」になるのでしょうか。
何故「ア」が正解になるのでしょうか。

お手数お掛けしますが、ご存知の方おられましたら、ご教授お願いします。

以上、よろしくお願い致します。

No.3 ベストアンサー 回答者： jjon-com 回答日時： 2010/12/10 01:44

>「終端記号」と「非終端記号」は、何処を見て判断するのですか。

< > で囲まれているのが終端記号で，囲まれていないのが非終端記号。
非終端記号として < や > というメタキャラクタ自体を使いたければ '<' や '>' と表記する。

この回答へのお礼

ご回答ありがとうございます。

「終端記号」と「非終端記号」の見分け方が分かりました。
これで再帰的に処理が出来るか出来ないかの判断が出来るのですね。

非常に丁寧に説明して頂き、ありがとうございました。

以上、ありがとうございました。

お礼日時：2010/12/10 15:36

No.2 回答者： jjon-com 回答日時： 2010/12/10 00:14

<S>::=01|0<S>1

上記のバッカス記法(BNF)が意味することは次のとおり。

非終端記号 <S> とは，
(規則a) 終端記号 01 である
または
(規則b) 非終端記号を含む定義 0<S>1 である
のどちらか。

終端記号とはその名のとおり定義はそこで終わるものでそれ以上展開されることはない。
非終端記号とはその名のとおり定義はそこで終わらずその中をさらに展開できるもので，(規則b)のように，自分の定義の中に自分自身が含まれている「再帰的な定義」ができることが特徴である。

よって<S>とは，
（以下，分かりやすさのために丸括弧を用いるが本来は不要）

(規則a)だけで得られる結果は【01】
(規則b)→(規則a)の順に展開した結果は，
　　0<S>1→【0(01)1】
(b)→(b)→(a)の順に規則が適用されたなら，
　　0<S>1 →0(0<S>1)1 →【0(0(01)1)1】
(b)→(b)→(b)→(a)という規則適用なら，
　　0<S>1 →0(0<S>1)1 →0(0(0<S>1)1)1 →【0(0(0(01)1)1)1)1】

以下，省略。このようなパターンに該当するのは，ア。

この回答へのお礼

ご回答ありがとうございます。

お陰様で解釈することが出来ました。

「終端記号」は、それ以上展開されることはない。
「非終端記号」は、そこで終わらず更に展開が出来る。
「再帰的な定義」が出来る所がポイントなんですね。

更に質問で恐縮ですが、
「終端記号」と「非終端記号」は、何処を見て判断するのですか。

お手数お掛けしますが、ご教授お願いします。

以上、よろしくお願い致します。

お礼日時：2010/12/10 00:51

No.1 回答者： Tacosan 回答日時： 2010/12/09 18:25

「自力で調べた」結果として, 何が分かってどこが理解できないのですか?

「何故「01」を代入すると「0011」になるのでしょうか。」という疑問からすると, そもそも「0<S>1」が何を意味するかというところから理解できていないような気がするのですが.

この回答への補足

補足させて頂きます。

「<S>::=01|0<S>1」の右辺<S>に「01」を挿入すると、
「<S>::=01|0011」になります。そこまでは分かりました。
しかし何故それが「000111」になるかが分かりません。

お手数お掛けしますが、ご教授お願いします。

以上、よろしくお願い致します。

補足日時：2010/12/09 22:20

この回答へのお礼

ご回答ありがとうございます。

「0<S>1」の意味は分かりません。
BNF(バッカス)記法全体が分からないのです。

「<S>::=01|0<S>1」が、
「<S>」は「01」または「0<S>1」と解釈しました。
しかしその意味が全く分かりません。
それはどのような意味を持っているのでしょうか。

お手数お掛けしますが、解説お願いします。

以上、よろしくお願い致します。

お礼日時：2010/12/09 22:06