上下文无关语言的闭包性质
我有以下问题：
语言 L1 = {a^n * b^n : n>=0} 和 L2 = {b^n * a^n : n>=0} 是 上下文无关语言，因此它们在 L1L2 下是封闭的，因此 L={a^n * b^2n A^n : n>=0} 也必须是上下文无关的，因为它是由 a 生成的 闭包属性。
我必须证明这是否属实。 所以我检查了 L 语言，我不认为它是上下文无关的，然后我还看到 L2 只是 L1 的反转。
我是否必须检查 L1、L2 是否是确定性的？
I have the following problem:
Languages L1 = {a^n * b^n : n>=0} and L2 = {b^n * a^n : n>=0} are
context free languages so they are closed under the L1L2 so L={a^n *
b^2n A^n : n>=0} must be context free too because it is generated by a
closure property.
I have to prove if this is true or not.
So I checked the L language and I don’t think that it is context free then I also saw that L2 is just L1 reversed.
Do I have to check if L1, L2 are deterministic?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
L1={anbn ：n>=0} 和 L2={bnan ： n>=0} 都是
上下文无关。
由于上下文无关语言在串联下是封闭的，因此 L3=L1L2 也是上下文无关的。
然而，L3 与 L4={anb2nan : n >= 0} 不是同一种语言。
字符串 abbbaa 位于 L3 中，但不在 L4 中。
那么 L4 是上下文无关的吗？如果是这样，它必须遵守上下文无关语言的泵引理。
令 p 为 L4 的泵浦长度。选择 s = apb2pap。
那么s在L4中，并且|s| > p。因此，如果 L4 是上下文无关的，我们可以写成
作为 uvxyz，带有 |vxy| <= p, |vy| >= 1，并且 uvnxynz 在 L4 中
任何 n >= 0。
观察 L4 中任何非空字符串的以下属性： a 的计数等于 b 的计数。子字符串 'ab' 恰好出现 1 次，并且恰好出现 1 次
子字符串“ba”的出现。 a 的初始字符串的长度等于 a 的最终字符串的长度。
我们可以使用这些观察结果来限制 L4 泵浦论证中 v 和 y 的可能选择。 v 和 y 都不能包含子字符串“ab”，因为这样，当 v 和 y 被泵送任意次数时，输出字符串将包含多次出现的“ab”，因此不能是 L4 的元素。同样的论点也适用于子字符串“ba”。
因此 v 必须为空、全部为 a 或全部为 b。这同样适用于 y。
此外，如果 v 全部为 a，则 y 必须由相同数量的 b 组成；否则，泵送的字符串将包含不相等数量的 a 和 b，因为 v 和 y 是由
相同的n。同样，如果 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 不是上下文无关的。
L1={anbn : n>=0} and L2={bnan : n>=0} are both
context free.
Since context-free languages are closed under concatenation, L3=L1L2 is also context-free.
However, L3 is not the same language as L4={anb2nan : n >= 0}.
The string
abbbaais in L3, but not L4.So is L4 context-free? If so, it must obey the pumping lemma for context-free languages.
Let p be the pumping length of L4. Choose s = apb2pap.
Then s is in L4, and |s| > p. Therefore, if L4 is context-free, we can write s
as uvxyz, with |vxy| <= p, |vy| >= 1, and uvnxynz is in L4 for
any n >= 0.
Observe the following properties of any nonempty string in L4: The count of a's equals the count of b's. There is exactly one occurrence of the substring 'ab', and exactly one
occurrence of the substring 'ba'. The length of the initial string of a's equals the length of the final string of a's.
We can use these observations to constrain the possible choices of v and y in our pumping argument for L4. Neither v nor y can contain the substring 'ab', because then, as v and y are pumped an arbitrary number of times, the output string would contain multiple occurrences of 'ab', and therefore cannot be an element of L4. The same argument applies to the substring 'ba'.
So v must be either empty, all a's, or all b's. The same applies to y.
Furthermore, if v is all a's, then y must consist of the same number of b's; otherwise, the pumped string would contain unequal numbers of a's and b's since v and y are pumped by
the same n. Likewise, if v is all b's, then y must be the same number of a's.
But if v is all a's, and y is all b's, the final string of a's is unaffected by pumping v and y, therefore the leading string of a's will no longer match the trailing string of a's.
Similarly, if v is all b's and y is all a's, the leading and trailing strings of a's will again have different lengths as v and y are pumped.
v and y cannot both be empty, since that would violate the condition |vy| >= 1 for
the CFL pumping lemma. But since we have established that |v| = |y|, it follows
that neither v nor y can be empty.
But if v cannot be empty, cannot be all a's, cannot be all b's, and cannot contain
the substrings 'ab' or 'ba', then there is no possible choice of uvxyz for which
the pumped version of s is still in L4. Therefore L4 is not context-free.
我不确定它是 - 请注意，在
L1和L2的每个定义中，n的范围都在该定义内，即它们是两个不同的变量。当你组合它们时，你应该重命名其中一个，然后得到：这是一种与你的
L非常不同的语言，但它显然是一种上下文无关的语言。I'm not sure that it is -- note that in each of the defintions of
L1andL2,nis scoped within that definition, i.e. they are two different variables. When you combine them you should rename one, and get instead:This is a very different language from your
L, but it is obviously a context free one.