令 L1={a^nb^mc^(n+m) / n,m > 0} 且 L2={a^nb^nc^m / n,m > 0}。是否 L3= L1 ∩ L2 context-free或不？
Let L1={a^nb^mc^(n+m) / n,m > 0} and L2={a^nb^nc^m / n,m > 0}.Is L3= L1 ∩ L2 context-free or not?
令 L1={a^n b^m c^(n+m) / n,m > 0} 且 L2={a^n b^n c^m / n,m > 0}。L3= L1 ∩ L2 context-free 与否?
我的逻辑是如果 n < m 交集将产生一种语言 (a^n b^n c^n) 如果 n > m 交集将产生一种语言 (a^n b^m c^m) 在这两种情况下我们有一个 CFG，所以我的解释正确吗？
我不确定我是否正确理解了您的想法，但是如果您尝试对 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=anbm 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不能算（不止一次，an b n 可以）。但是为了实现模式n,n,2n，我们必须计算a和b的数量，然后添加适量的c。
- 泵引理：我们必须否定原始引理以证明 {an bn c2n | n > 0} 不是 CFG。所以我们需要证明对于每个 p >= 0 都有一个 s ∈ {an b n c2n | n > 0} 不能拆分成 uvwxy fullfilling |uvw| <= p and uvkwxk y ∈ {an bn c2n | n > 0}.
证明：给定 p >= 0。我们选择单词 t = ap bp c2p ∈ L1 ∩ L2。现在，对于 uvwxy = t 的每个选择，我们都无法将 uvwxy 抽取为 ∈ L1 ∩ L2。这是因为我们只泵 v 和 x。还有|vwx|是 <= p。所以 vwx 不能包含 a、b 和 c，但最多包含两个。现在，如果我们抽取 v 和 x，我们得到的 a 多于 c，反之亦然，结果 uv2wx2y不在L1∩L2.
令 L1={a^n b^m c^(n+m) / n,m > 0} 且 L2={a^n b^n c^m / n,m > 0}。L3= L1 ∩ L2 context-free 与否?
我的逻辑是如果 n < m 交集将产生一种语言 (a^n b^n c^n) 如果 n > m 交集将产生一种语言 (a^n b^m c^m) 在这两种情况下我们有一个 CFG，所以我的解释正确吗？
我不确定我是否正确理解了您的想法，但是如果您尝试对 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=anbm 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不能算（不止一次，an b n 可以）。但是为了实现模式n,n,2n，我们必须计算a和b的数量，然后添加适量的c。
- 泵引理：我们必须否定原始引理以证明 {an bn c2n | n > 0} 不是 CFG。所以我们需要证明对于每个 p >= 0 都有一个 s ∈ {an b n c2n | n > 0} 不能拆分成 uvwxy fullfilling |uvw| <= p and uvkwxk y ∈ {an bn c2n | n > 0}.
证明：给定 p >= 0。我们选择单词 t = ap bp c2p ∈ L1 ∩ L2。现在，对于 uvwxy = t 的每个选择，我们都无法将 uvwxy 抽取为 ∈ L1 ∩ L2。这是因为我们只泵 v 和 x。还有|vwx|是 <= p。所以 vwx 不能包含 a、b 和 c，但最多包含两个。现在，如果我们抽取 v 和 x，我们得到的 a 多于 c，反之亦然，结果 uv2wx2y不在L1∩L2.