生成语言L的BNF文法
BNF grammar that generates language L
我花了很多时间，但仍然无法理解如何解决这个问题。我有答案。你能告诉我他是怎么想出来的吗？
是否有我可以遵循的特定规则或标准结构？我知道并集和串联的规则，但不知道它们颠倒时的规则。
如果 x 是 y 的（可能不正确的）子串，那么 x^r c y 可以写成 x^R c wxz 其中 w 和 z 是 (a+b)*.
上的任意字符串
现在我们可以尝试"slice"这种语言的字符串，看看它们是如何被CFGs生成的。非常规部分是确保 x^R 和 x 正确；其余的都是微不足道的。所以我们需要一些规则，例如：
S -> aXa | bYb | c
这给了我们 x^R c x。我们缺少 w 和 z。我们可以通过让任意字符串出现在 c:
之后来添加 w
S -> aSa | bSb | cA
A -> aA | bA | e
我们可以通过将 S 更改为 T 并添加一个新的 S 来获得 z，它会产生 T 后跟任何内容：
S -> TA
T -> aTa | bTb | cA
A -> aA | bA | e
我们所忽略的只是 |x| > 1。我们通过将 T -> cA 更改为两个作品 T -> acAa | bcAb 来做到这一点。这会产生建议的语法（不是唯一正确的语法，只有一种有效的语法）并解释我们如何到达那里。
我花了很多时间，但仍然无法理解如何解决这个问题。我有答案。你能告诉我他是怎么想出来的吗？
是否有我可以遵循的特定规则或标准结构？我知道并集和串联的规则，但不知道它们颠倒时的规则。
如果 x 是 y 的（可能不正确的）子串，那么 x^r c y 可以写成 x^R c wxz 其中 w 和 z 是 (a+b)*.
现在我们可以尝试"slice"这种语言的字符串，看看它们是如何被CFGs生成的。非常规部分是确保 x^R 和 x 正确；其余的都是微不足道的。所以我们需要一些规则，例如：
S -> aXa | bYb | c
这给了我们 x^R c x。我们缺少 w 和 z。我们可以通过让任意字符串出现在 c:
w
S -> aSa | bSb | cA
A -> aA | bA | e
我们可以通过将 S 更改为 T 并添加一个新的 S 来获得 z，它会产生 T 后跟任何内容：
S -> TA
T -> aTa | bTb | cA
A -> aA | bA | e
我们所忽略的只是 |x| > 1。我们通过将 T -> cA 更改为两个作品 T -> acAa | bcAb 来做到这一点。这会产生建议的语法（不是唯一正确的语法，只有一种有效的语法）并解释我们如何到达那里。