拡張ＢＮＦの解釈を教えて

質問

<P>::=<P><P>|'('<P>')'|'['<P>'}'|'<'<P>'>'|'a'|'b'|'c'　に関して、<P>の表す記号列集合を｛<P>｝とし、記号列Wが｛<P>｝に属する事をw∈｛<P>｝と表す。次の内の何れが誤りですか。
１.'a'∈｛<P>｝
２.'(a)'∈｛<P>｝
３.'<a><b>'∈｛<P>｝
４.｛<P>｝に属する記号列の長さは奇数長のものもある。
５.｛<P>｝に属する記号列は左から読んでも右から読んでも同じである。

回答No.5

ymmasayan

No.1、No.3のymmasayanです。

＞<P>::=<P><P>
＞で右辺の<P>が同じものでないといけないとすると、
＞expression::=term+term
＞という表現ができなくなりませんか？

左辺のの<Ｐ>を右辺に代入して、新しい左辺の<Ｐ>が出来上がるわけです。
これを何度繰り返してもいいのです。
したがってＢＮＦを厳密に読めば、
expression::=expression+expressionということに成るような気がします。

<Ｐ>::=<Ｐ１><Ｐ２>が許されるかどうかですね。これが許されればａｂもでてくるのですがね。
これをやろうとすればＢＮＦの文法をもう一行追加すればいいだけだと思います。

回答No.4

kaitou-man

<P>::=<P><P>
で右辺の<P>が同じものでないといけないとすると、
expression::=term+term
という表現ができなくなりませんか？

回答No.3

ymmasayan

No.1のymmasayanです。
結論が割れましたね。そこで若干補足です。

ポイントは<P>::=<P><P>の部分です。
記号列が増殖する（長くなる）のはここしかありません。ここは再帰構造をとっています。
増殖する場合は同じ記号列（記号）を接続することしか出来ません。
他の記号列部分はすべて左右対称ですから、増殖時も左右対称になります。

したがってａｂという非対称の記号列ができることはありません。

いずれにしても他の方の回答を待ちたいですね。

回答No.2

kaitou-man

結論が違いますが、５が誤りですね。
'<a>'∈｛<P>｝
'<b>'∈｛<P>｝
より、
'<a><b>'∈｛<P>｝
です。

回答No.1

ymmasayan

３が誤りです。

１，２，４はいいとして３と５は完全に矛盾しています。
５の左右対称が正しくて、３の'<a><b>'は作り様がありません。