1

学習目的で「文脈自由文法を作成するためのヒント」の投稿を読んでいて、概念はほぼ理解していますが、次のことはよくわかりません。

私たちが持っている場合：

L = {a m b n | m >= n}。

これは分かります：

S --> B
B --> aBb
A  --> aA

しかし、私が理解していないのは、次のような特定の値の末尾に追加するという概念です。

S --> B | ^
B --> aBb | A
A  --> aA | a

これらの行の末尾に^ (null)、A、およびaを追加するのはなぜですか? 彼らは何をし、なぜ彼らが必要なのですか？

すべてのヘルプは大歓迎です。

4

2 に答える 2

2

言語にある文字列を構築できるようにするために、それらが必要ですL。

B --> aBb | Aは、非終端記号がある場合、またはBで置き換えることができることを意味します。(大文字は非終端記号を表し、小文字は終端記号を表します)。aBb A

文法を見てみましょう：

S --> B | ^
B --> aBb | A
A  --> aA | a

なぜ私たちは持っているの| ^ですか？空の文字列を生成できるようにするために必要です。空の文字列はL、同じ量の と が含まれているためa、明らかに言語の一部ですb。

なぜ私たちは持っているの| Aですか？のルールを使用できるようにしますA。に置き換えることがBできるので、 または のいずれかA を挿入できます。s よりもsが多い文字列を生成できるようにするには、このルールが必要です。aAaab

なぜ私たちは持っているの| aですか？置換が必要な新しい非終端記号を追加Aせa ずに置換できるようにする。

この文法を見ると、 s とs の量が等しい文字列を生成できるように変更A --> aA | aする必要があると言えます。(したがって、余分な を追加する代わりに、空の文字列 (または null) に置き換えることができます)A --> aA | a | ^abAa

文字列を生成したいとしましょうaaabb：

S       //You start with S
B       //Rule: S --> B
aBb     //Rule: B --> aBb
aaBbb   //Rule: B --> aBb
aaAbb   //Rule: B --> A
aaabb   //Rule: A --> a
于 2013-04-13T02:46:29.997 に答える