2

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

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

那些人的联合呢？（这显然是非常规的）它是上下文无关的吗？

4

1 回答 1

3

我们选择语言 U = {a^ib^jc^k | 作为我们的宇宙。i, j, k 在 N} 中。

那么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 intersect L_2^C)^C。通过 DeMorgan，我们可以将其渲染为 L_B^C union 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。

于 2012-02-22T15:09:52.417 回答