上下文无关语言的闭包属性 [英] Closure properties of context free languages

问题描述

我有以下问题：

语言L1 = {a ^ n * b ^ n：n> = 0}和L2 = {b ^ n * a ^ n：n> = 0}是
上下文无关的语言，因此它们在L1L2下关闭，因此L = {a ^ n *
b ^ 2n A ^ n：n> = 0}也必须是上下文无关的，因为它是由
闭包属性生成的。

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.

我必须证明是否是否正确。
所以我检查了L语言，但我认为它不是上下文无关的，所以我还看到L2只是L1反转了。

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.

我有吗检查L1，L2是否具有确定性？

Do I have to check if L1, L2 are deterministic?

推荐答案

L1 = {a ⁿ b ⁿ ：n> = 0}和L2 = {b ⁿ a ⁿ ：n> = 0}都是
上下文无关的。

L1={aⁿbⁿ : n>=0} and L2={bⁿaⁿ : n>=0} are both context free.

由于上下文无关的语言在连接时关闭，因此L3 = L1L2也是上下文无关的。

Since context-free languages are closed under concatenation, L3=L1L2 is also context-free.

但是，L3与L4 = {a ⁿ b ²ⁿ a ⁿ ：n> = 0}。
字符串 abbbaa 在L3中，但不在L4中。

However, L3 is not the same language as L4={aⁿb²ⁿaⁿ : n >= 0}. The string abbbaa is in L3, but not L4.

那么L4是否与上下文无关？如果是这样，它必须遵守为上下文无关的语言抽取引理。

So is L4 context-free? If so, it must obey the pumping lemma for context-free languages.

让p为L4的抽运长度。选择s = a ^p b ^2p a ^p 。
然后s在L4中，并且| s | >第因此，如果L4是上下文无关的，我们可以用| vxy |将s
写为uvxyz。 < = p，| vy | > = 1，并且uv ⁿ xy ⁿ z在L4中对于
任意n> = 0。

Let p be the pumping length of L4. Choose s = a^pb^2pa^p. 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 uvⁿxyⁿz is in L4 for any n >= 0.

观察L4中任何非空字符串的以下属性：a的计数等于b的计数。子字符串 ab恰好出现一次，子字符串 ba恰好出现一次
。 a的初始字符串的长度等于a的最终字符串的长度。

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.

我们可以使用这些观察值来约束抽水中v和y的可能选择L4的参数。 v和y都不能包含子字符串 ab，因为那样，由于v和y被任意泵送多次，输出字符串将包含多次出现的 ab，因此不能是L4的元素。相同的参数适用于子字符串 ba。

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'.

因此v必须为空，全为a或全为b。 y也是如此。

So v must be either empty, all a's, or all b's. The same applies to y.

此外，如果v都是a，则y必须由相同数量的b组成；否则，由于v和y由相同的n抽取
，所以抽取的字符串将包含不相等的a和b。同样，如果v是所有b，那么y必须与a相同。

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.

但是，如果v是所有a，而y是所有b，则最后一个字符串a不受泵v和y的影响，因此a的前导字符串将不再与a的尾随字符串匹配。
同样，如果v都是b，而y都是a，则随着v和y的抽运，a的开头和结尾字符串的长度将再次不同。

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和y不能都为空，因为那样会违反条件| vy |。 > = 1 for
CFL泵引理。但是，既然我们已经确定了| v | = | y |，则
后面的v和y都不能为空。

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.

但是，如果v不能为空，则不能全部为a，也不能全部为空b，并且不能包含
子字符串'ab'或'ba'，则没有uvxyz的选择，对于s的泵浦版本
仍在L4中。因此L4不是上下文无关的。

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.

这篇关于上下文无关语言的闭包属性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！