我是一名助教，一位学生向我提出了以下问题。尴尬的是，我无法想出答案，所以我向你们求助。
我们知道 L_1 = {a^n b^n c^n} 是非 CFL。 我们还知道 L_2 = {a^i b^k c^j : i != k } 上下文无关。
那些的联合怎么样？ (这显然是不规则的) 它是上下文无关的吗？
最佳答案
我们选择语言 U = {a^i b^j c^k | N 中的 i、j、k}。
则 L_1^C = {a^i b^j c^k | i!=j 或 j!=k} = {a^i b^j c^k | i!=j} 并集 {a^i b^j c^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)并集(L_B 与 L_2^C))^C 相交。
回想一下，由于 L_A = L_2，我们得到 (L_B intersect L_2^C)^C。根据 DeMorgan，我们可以将其呈现为 L_B^C 并集 L_2。我们已经承认 L_2 是上下文无关的。我们宇宙中 L_B 的补集是 {a^i b^j c^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。
在 bool 逻辑中:(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。
关于automata - 以下 CFL 和非 CFL 的并集是 CFL 本身吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9395964/