context-free-language - 证明以下语言不是上下文无关的

Question

L = {a^ib^jc^k; i≠j 和 i≠k 和 j≠k}。

第一种方法：我尝试了两个不同的字符串来通过抽取引理来证明它，但它们都不正确。第一个 w = a^mb^m+1 c^m+2 和 m 是泵送长度。例如 w = uvxyz 的一种情况是 vxy in 是一部分。所以 w = a^mk a^kb^m+1 c^m+2 对于任何 i >=0 它必须在 L wi = a^mk a^ik b^m+1 c^m+2 中。我不能证明 a 的数量等于 b 的数量。

第二种方法：我将 L 转换为 6 种不同语言的并集 {a^ib^jc^k U a^ib^kc^j U a^jb^ic^k U a^jb^kc^i U a^kb^ic ^j U a^kb^jc^i ; 一世

Answer 1

我找到了答案。

如果我们选择 W=a^m! b^(m+1)！c^(m+2)! 然后我们可以证明它。

我正在解决 uxy 在 a 方面的情况。那么 W= a^m!-ka^kb^(m+1)! c(m+2)！我们知道存在一个整数 x = m！m / k for 1<= k <= m 所以我们选择 i = (1+x) 然后 m！+ kx = 米！+米！米=米！(m+1) = (m+1)！表示 a 的数量 = b 的数量，这意味着该字符串不在 L 中。这是一个矛盾。