context-free-grammar - 确定给定的语言是否为常规/上下文无关/非上下文无关

Question

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

假设我有以下语言:

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，我们可以构建一个 DFA，它根本不接受“abc”，因此是常规的。

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 个以上的比较，我们需要更多堆栈。

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

提前致谢

Answer 1

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