考虑下面的BNF语法(BNF，递归)

Question

编写一个BNF语法，用于识别所有形式为anbn-2的句子，其中n>1。
例如，aa、aaab、aaaabb都可以接受，
但abbb、aab、aabb不可以
(提示:使用递归)。

这是我的推导:
S::= AZ
Z::= A | AAB
A::= A
B::= B
这是正确的吗?

EDIT:也许这是正确的?

S→a | X | Y
X->a
Y ->aX | b

Answer 1

两个都是完全错误的。

第一个语法:由于A只能变成A, B只能变成B，我们可以用A代替A，用B代替B。语法将是:

S -> aZ
Z -> a
Z -> aab

因此，S变为aa或aaab，但不是，例如，aaaabb。

第二个语法:使用第一个规则，把S变成a。因为a不是一个有效的单词，所以语法也是不正确的。(或者，我们可以将S转换为X，然后将X转换为aX 9次，然后将X转换为a，生成aaaaaaaaaa，这也是无效的)

Answer 2

你的第一个语法只产生:

S -> AZ -> aZ -> aa
S -> AZ -> aZ -> aAAB -> aaab

您的第二个语法允许只包含a的单词，它不是语言的一部分。例如:

S -> a

我简单地从两个a开始，然后产生任意对。因此，语法看起来像(BNF语法):

<term> ::= "aa" | "aa" <pair>
<pair> ::= "ab" | "a" <pair> "b"

的例子:

<term> -> "aa"
<term> -> "aa" <pair> -> "aaab"
<term> -> "aa" <pair> -> "aaa" <pair> "b" -> "aaaabb"
...