识别常规语言

我很难识别常规语言。识别常规语言

我知道，如果R是一个正则语言然后如果A = RR，由于为R的串联因此A为正则语言

但是B = {WW | w < - R}定期？

我的第一个直觉是肯定的。因为它也是R的串联。但是因为它是串联的一个子集，所以我觉得我不能以这种方式证明它。然后我在想，因为w是一个正则语言的字符串，它是单体的连接，然后是它们的连接......我知道我已经完全脱离了轨道，因为如果这样想，那不是什么？现在我更倾向于说它不是。因为我真的找不到它的正则表达式。我想尝试使用抽象引理，但很难适用于这个例子。

任何人都可以提供一些建议吗？即使是正确的轨道让我遵循将是伟大的？

来源

2011-10-23 lynnyilu

继续尝试抽吸引理。先从一个非常简单的正则表达式，例如：

R = ab*

因为此时你正试图证明它是不规律的，你需要的是一个反例。所以你可以选择任何你想要的R。（以上都可以正常工作。）

来源

2011-10-23 08:24:16

谢谢你的帮助！我工作过，只能确认我的推理，因为我怀疑它：如果R = ab *和w <-R， B = {ww | w <-R}不是（a^p）b（a^p）b < - B的长度大于p的长度，因此如果我们假设它是，并且p是抽吸长度，则通过抽吸引理（a^p）b^p）b = xyz，其中xy^iz在B中对于所有i> = 0，因为| xy | y =完全由'a'组成。但然后xyyz不在D所以这是一个矛盾因此，它不是正规的 – lynnyilu

看起来不错（我不得不检查抽水引理，这是一段时间...） –

哈哈听起来好吧是够好的。谢谢 – lynnyilu

识别常规语言

回答

相关问题