考虑以下BNF语法(BNF，递归)

Question

编写一个BNF语法，用于识别所有的句子，形式为anbn-2，其中n>1。

例如，aa，aaab，aaaabb都被接受了，

但abbb，abbb

(提示:使用递归)。

这是我的推论：

S ::= AZ

Z ::= A= AAB

A ::= a

B ::= b

这是正确的吗？

编辑：也许这是正确的？

S -> a_x_x_y

                                                                                       X-> aX | a      

                                                                                               Y -> aX | b

Answer 1

两者都是完全不正确的。

第一种语法:由于A只转到a，而b只转到b，所以我们可以用a和b替换A和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的单词，这些单词不是语言的一部分。例如：

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"
...