gpt4 book ai didi

computer-science - CFL 的泵引理

转载 作者:行者123 更新时间:2023-12-04 08:32:26 26 4
gpt4 key购买 nike

我的问题是:

令 L = { {a,b} 中的 x * | x 具有相等数量的 a 和 b}

我知道这是一种上下文无关语言,因为我可以为它创建语法(e 是 epsilon):

S -> aX | bY | e

X -> bS | aXX

Y -> aS | bYY

您还可以通过使用与常规语言相交的上下文无关语言是上下文无关的事实来证明它是上下文无关的。

由于它是一种上下文无关语言,根据 CFL 的抽取引理,任何长于抽取长度 p 的字符串都应该能够被抽取。但是,如果我选择字符串 s = a^p b^p a^p b^p,则无法抽取该字符串,因此该语言不应该是上下文无关的。

我哪里错了?

最佳答案

当然可以抽绳。令 u = a^p b^(p-1), v = b, x = e, y = a, z=a^(p-1) b^p。现在 uvxyz = s 并且对于任何 i u v^i x y^i z 具有相等数量的 as 和 bs。

关于computer-science - CFL 的泵引理,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1316833/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com