以下 CFL 和非 CFL 的并集是 CFL 本身吗？

Question

我是一名助教，一位学生问我以下问题。尴尬的是，我无法想出答案，所以我向你们求助。

我们知道 L_1 = {a^nb^nc^n} 是非 CFL。 我们还知道 L_2 = {a^ib^kc^j : i != k } 上下文无关。

那些人的联合又如何呢？ （这显然是不规则的） 它是上下文无关的吗？

Answer 1

我们选择语言 U = {a^ib^jc^k | N 中的 i、j、k}。

那么 L_1^C = {a^ib^jc^k | i!=j 或 j!=k} = {a^ib^jc^k | i!=j} 并集 {a^ib^jc^k | j != k} = L_A 并集 L_B。请注意，L_A = L_2。

根据 DeMorgan，L_1 union L_2 = (L_1^C intersect L_2^C)^C = ((L_A union L_B) intersect L_2^C)^C，根据分配律是 ((L_A intersect L_2^C) union (L_B与 L_2^C))^C 相交。

回想一下，由于 L_A = L_2，我们得到 (L_B 与 L_2^C)^C 相交。根据 DeMorgan，我们可以将其呈现为 L_B^C 并集 L_2。我们已经承认 L_2 是上下文无关的。我们宇宙中 L_B 的补码是 {a^ib^jc^k | j=k}，这也是上下文无关的。两种上下文无关语言的并集也是上下文无关的，所以是的，L_1 并集 L_2 是上下文无关的。

完成手续后，直觉就很明显了：L_1 union L_2 相当于说 i != j（a 和 b 的数量不同）或者 b 和 c 的数量相同。如果你仔细想想，这完美地捕捉了语言的要求：如果 i != j，我们就可以完成第二部分；我们无法进入 L_2 的唯一方法是，如果我们已经知道 i = j，并且我们只需担心保证 j = k。

在布尔逻辑中：(a and b) or (not a) 等价于(b or (not a))。

该语言的 CFG 如下：

S := A | C
A := aA | B
B := lambda | bBc
C := Cc | D | E
D := a | aD | aDb
E := b | Eb | aEb

您可以通过自上而下或自下而上的解析器构造获得 PDA。