为什么秒 - > ^和A - >一个？在上下文无关文法(Why s-->

我一直在读： “有关创建上下文无关文法”学习之用，我几乎理解这个概念后，但我不太明白以下。

如果我们有：

米> = N}。

我明白这一点：

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

但我不明白的是增加这些特定的值，比如年底的概念：

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

为什么我们加^（空），A， 和这些行的结束？他们在做什么，为什么我们需要它们？

所有帮助是极大的赞赏。

Answer 1:

你需要他们能够构建在语言的字符串L 。

B --> aBb | A B --> aBb | A手段，如果你有一个非终结符B它可以通过替换aBb 或 A 。（大写字母表示非终结符和小写字母表示终端）。

让我们来看看语法：

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

为什么我们有一个| ^ | ^ ？ 你需要它能够产生空字符串。空字符串是明确语言的一部分L ，因为它包含的等量的a S和b秒。

为什么我们| A | A ？ 为了能够使用规则A 。现在，您可以代替B有A让您可以插入或者aA或a 。你需要这个规则能够生成具有多个字符串a总比b秒。

为什么我们| a | a ？ 为了能够更换A带有a 不增加新的非终结需要更换。

当我看到这个语法我要说的是，你需要改变A --> aA | a A --> aA | a到A --> aA | a | ^ A --> aA | a | ^ A --> aA | a | ^能够与等量的生成字符串a S和b秒。（所以你可以更换A用空字符串（或空），而不必添加额外的a ）

比方说，你要生成的字符串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