设L1 = {a ^ nb ^ mc ^（n + m）/ n，m> 0}，L2 = {a ^ nb ^ nc ^ m / n，m> 0}。这是L3 =L1∩L2无上下文或不？

Question

设L1 = {a ^ nb ^ mc ^（n + m）/ n，m> 0}，L2 = {a ^ nb ^ nc ^ m / n，m> 0}。这是L3 =L1∩L2无上下文或不？

我的逻辑是，如果n <m交叉将产生一种语言（a ^ nb ^ nc ^ n），如果n> m，交叉将产生一种语言（a ^ nb ^ mc ^ m），在这两种情况下我们都有一个CFG所以我的解释是正确的吗？

Answer 1

我不确定我是否理解你的想法，但如果你尝试对L1和L2使用相同的n和m并根据它计算交点，那你就不对了。

除此之外，语言{an bn cn | n> 0}不是CFG，因为你可以在这里看一个例子https://en.wikipedia.org/wiki/Context-free_language或使用泵浦引理显示。

怎么能看到L1∩L2的样子？ x∈L1∩L2<=>x∈L1和x∈L2。所以x必须满足两种语言的限制。 因此，x∈L1∩L2是x = a bm co，其中n = m，因为L2和o = n + m = n + n（n + m，因为L1和n + n，因为n = m）。 这给了我们L1∩L2= {an bn c2n | n> 0}，这不是CFG。

原因：

• 直观地说，CFG不能算数（不止一次，bn就好了）。但是为了实现模式n，n，2n，我们必须计算a和b的amoung，然后加上适量的c。
• 抽取引理：我们必须否定原始引理，以显示{a bn c2n | n> 0}不是CFG。所以我们需要证明，对于每个p> = 0，都有一个s∈{an bn c2n | n> 0}不能分成uvwxy fullfilling | uvw | <= p和uvkwxky∈{an bn c2n | n> 0}。 证明：给定p> = 0.我们选择单词t = ap bpc2p∈L1∩L2。现在，对于uvwxy = t的每一个选择，我们都不能将uvwxy泵送到∈L1∩L2。这是因为我们只抽v和x。并且| vwx |是<= p。所以vwx不能包含a，b和c，但最多只能包含两个。现在，如果我们抽v和x，我们得到的数字多于c，反之亦然，结果uv2wx2y不在L1∩L2。