4

我需要一些帮助来确定给定的语言是常规的、上下文无关的还是非上下文无关的。答案中简短的非正式解释就足够了，因此无需使用抽水引理。

可以说我有以下语言：

L1 = { w ∈ {a, b, c, d}* | #a(w) is even, #b(w) = 1 mod 3, w does not have 
                           a substring abc }

L2 = { w  ∈ {a, b, c, d}* | #a(w) is even, #b(w) < #c(w) }

L3 = { w  ∈ {a, b, c, d}* | #a(w) < #b(w) < #c(w) }

这是我的解决方案：

L1 = L2 ∩ L3 ∩ L4 where

L2 = #a(w) is even
L3 = #b(w) = 1 mod 3
L4 = w does not have a substring abc

可以为 L2 构造一个 DFA，因为 L2 不需要无限的内存，所以 L2 是规则的。对于 L3 的推理与上述相同。对于 L4，我们可以构造一个根本不接受“abc”的 DFA，因此是常规的。

L1 是正则的，因为正则语言在 ∩ 下是封闭的。

对于 L2，我们可以将语言分为：

L2 = L3 ∩ L4 where

L3 = #a(w) is even
L4 = #b(w) < #c(w)

我们知道可以为 L3 构造 DFA，因此 L3 是规则的。L4 是上下文无关的，因为我们可以构建一个 PDA，其中堆栈用于计算 a:s 和 b:s 的数量。

L2 因此是上下文无关的，因为常规语言和上下文无关语言的 ∩ 导致上下文无关语言。

对于 L3，我们可以看到它是非上下文无关的，因为我们被限制为 1 个堆栈，并且要进行超过 1 个比较，我们需要更多的堆栈。

是我的推理权利吗？我很快就要考试了，需要知道我是否有这个想法。

提前致谢

4

1 回答 1

3

是的，你在所有三个方面都是正确的。L1 是常规的，L2 是上下文无关的，L3 不是上下文无关的。您正确地为 L1 和 L2 应用了闭包属性，并且您的推理对于最后一个或多或少是正确的。对于最后一个，我会提醒您不要使用该规则......因为可能有不止一种方法可以考虑如何识别一种语言，其中一些需要更多的堆栈，而其中一些不需要. 以非上下文无关语言 L = {a^nb^nc^n} 为例。这种语言的补充是与上下文无关的，尽管草率地应用您使用的规则可能会让您不相信（直到您正确考虑了这个问题）。

于 2013-01-03T17:08:37.920 回答