我有以下问题：
语言 L1 = {a^n * b^n : n>=0} 和 L2 = {b^n * a^n : n>=0} 是上下文无关语言，因此它们在 L1L2 下是封闭的，因此 L={a ^n * b^2n A^n : n>=0} 也必须是上下文无关的，因为它是由闭包属性生成的。
我必须证明这是否属实。所以我检查了 L 语言，我认为它不是上下文无关的，然后我还看到 L2 只是 L1 反转。
我是否必须检查 L1、L2 是否是确定性的？
问问题
2046 次
2 回答
4
L1={a n b n : n>=0} 和 L2={b n a n : n>=0} 都是上下文无关的。
由于上下文无关语言在连接下是封闭的，因此 L3=L1L2 也是上下文无关的。
但是，L3 与 L4={a n b 2n a n : n >= 0}不是同一种语言。字符串abbbaa在 L3 中，但不在 L4 中。
那么 L4 是上下文无关的吗？如果是这样，它必须遵守上下文无关语言的抽水引理。
令 p 为 L4 的泵送长度。选择 s = a p b 2p a p。那么 s 在 L4 中，并且 |s| > 页。因此，如果 L4 是上下文无关的，我们可以将 s 写成 uvxyz，用 |vxy| <= p, |vy| >= 1，对于任何 n >= 0，uv n xy n z 在 L4 中。
观察 L4 中任何非空字符串的以下属性： a 的计数等于 b 的计数。子串“ab”恰好出现一次，子串“ba”恰好出现一次。a's 的初始字符串的长度等于 a's 的最终字符串的长度。
我们可以使用这些观察结果来限制 v 和 y 在 L4 的抽水论证中的可能选择。v 和 y 都不能包含子字符串 'ab'，因为这样，当 v 和 y 被任意次数抽出时，输出字符串将包含多次出现的 'ab'，因此不能是 L4 的元素。相同的论点适用于子字符串 'ba'。
所以 v 必须要么是空的，要么全是 a，要么全是 b。这同样适用于 y。
此外，如果 v 都是 a，那么 y 必须由相同数量的 b 组成；否则，由于 v 和 y 被相同的 n 泵送，泵送的弦将包含不等数量的 a 和 b。同样，如果 v 都是 b，则 y 必须是相同数量的 a。
但是如果 v 都是 a，y 都是 b，则 a 的最后一个字符串不受抽吸 v 和 y 的影响，因此 a 的前导字符串将不再匹配 a 的尾随字符串。类似地，如果 v 都是 b 并且 y 都是 a，那么随着 v 和 y 的抽水，a 的前导和尾随字符串将再次具有不同的长度。
v 和 y 不能都是空的，因为这会违反条件 |vy| >= 1 对于 CFL 泵引理。但是既然我们已经确定了 |v| = |y|，因此 v 和 y 都不能为空。
但是如果 v 不能为空，不能全是 a，不能全是 b，并且不能包含子串 'ab' 或 'ba'，那么就没有可能的 uvxyz 选择，因为 s 的抽吸版本仍在 L4 中。因此 L4 不是上下文无关的。
于 2010-05-09T06:16:45.017 回答
0
我不确定是不是——请注意，在 and 的每个定义中L1，L2都n在该定义范围内，即它们是两个不同的变量。当你组合它们时，你应该重命名一个，然后得到：
L = {a^n * b^n b^m * a^m : n,m>=0}
这是一种与您的 非常不同的语言L，但它显然是一种上下文无关的语言。
于 2010-05-09T06:19:01.813 回答