1

我必须编写一个函数来检查输入字符串对于给定的语言规范是否有效。我认为这将是一个标准的 CFG -> Chomsky Normal Form，然后是 CYK 解析，但是语言中的一条规则是防止这种情况发生。

有些规则很简单，如果我们定义了 terminal {a,b,c,d,e,f,P,Q,R,S}，那么有效的字符串就是

1) 任何孤立的小写终端
2) 如果 'x' 是一个有效的字符串，那么 Sx 也是

但是第三条规则是

3) 如果 X 和 Y 是有效的输入字符串，那么 PXY、QXY、RXY 也是

其中{P,Q,R}是剩余的大写终结符，X 和 Y 是非终结符。

这个的生产规则是什么样的？我以为会是这样的

XY -> PXY (and QXY, RXY)

但这有两个问题。首先，这不是 CFG 规则——这是否意味着该语言定义了 CSG？

第二个是这行不通，因为

XY -> PXY -> PPXY

在所有情况下都不是有效的消息。

4

1 回答 1

3

我认为这个语法是上下文无关的，除非我误解了你在说什么。

首先，让我们让 A 成为扩展为仅使用前两个规则生成的某个有效字符串的非终结符，我们得到

A -> a | b | c | d | e | f

现在，您的第二条规则说，如果您可以构建字符串 ω，那么您就可以构建 Sω。我们可以将其编码为

A -> SA

最后，您说过如果您有两个字符串 X 和 Y，那么您可以将它们组合在一起为

PXY
QXY
RXY

考虑这一点的一种方法是生成字符串 P，后跟任意两个有效字符串（Q 或 R 相同）。因此您可以添加规则

A -> PAA | QAA | RAA

这给出了最终的语法

A -> a | b | c | d | e | f
A -> SA
A -> PAA | QAA | RAA

希望这可以帮助！

于 2012-05-07T03:16:42.327 回答