考慮以下BNF語法（BNF，遞歸）

Question

編寫一個BNF語法來識別anbn-2形式的所有句子，其中n> 1。
例如，aa，aaab，aaaabb全部被接受，
但abbb，aab，aabb不是
（提示：使用遞歸）。

這是我的推導：
S :: = AZ
Z :: = A | AAB
A :: = a
B :: = b
這是正確的嗎？

編輯：也許這是正確的？

S - > a | X | Y
X-> aX | 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轉換爲aX9次，然後將X轉換爲a，製作aaaaaaaaaa，這也是無效的）。

Answer 2

你的第一語法僅產生：

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

你的第二語法允許僅包含a的，這是不語言的一部分的話。例如：

S -> a 

我只是有兩個a的開始，然後產生任意對。因此，語法樣子（BNF syntax）：

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

實施例：

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