代码之家 › 专栏 › 技术社区 › Zac Uwyo H

生成语言L的BNF语法

formal-languages bnf context-free-grammar grammar

1

Zac Uwyo H · 技术社区 · 6 年前

我花了很多时间,但仍然不知道如何解决这个问题。我有答案。你能告诉我他是怎么想出来的吗?

我是否可以遵循特定的规则或标准结构?我知道并集和串联的规则,但不知道何时颠倒。

1 回复 | 直到 6 年前

1

0

Patrick87 6 年前

如果 x 是的子字符串(可能不正确) y 然后 x^r c y 可以写为 x^R c wxz 哪里 w 和 z 是否有任意字符串覆盖 (a+b)* .

现在,我们可以尝试对这种语言中的字符串进行“切片”,看看CFGs如何生成它们。非常规部分是确保 x^R 和 x个 正确地说出来;其余的都是微不足道的。所以我们需要一些规则,比如:

S -> aXa | bYb | c

这给了我们 x^R c x . 我们错过了 w 以及 z . 这个 w 我们可以在任意字符串之后添加 c :

S -> aSa | bSb | cA
A -> aA | bA | e

这个 z 我们可以通过改变 S 到 T 并添加新的 S 产生 T 后跟任何内容:

S -> TA
T -> aTa | bTb | cA
A -> aA | bA | e

我们所忽略的只是 |x| > 1 . 我们通过改变 T -> cA 到两个产品 T -> acAa | bcAb . 这就产生了建议的语法(不是唯一正确的语法,只有一种有效的语法),并解释了我们是如何做到这一点的。