两种不同字母的语言的交集是什么? [英] What is the intersection of two languages with different alphabets?

问题描述

我对此进行了一些谷歌搜索，但没有真正确定的弹出.

I did some googling on this and nothing really definitive popped up.

假设我有两种语言 A 和 B.

Let's say I have two languages A and B.

A = { w 是 {a,b,c}* 的子集，使得 w 的倒数第二个字符是 b }

A = { w is a subset of {a,b,c}* such that the second to the last character of w is b }

B = { w 是 {b,d}* 的子集，使得最后一个字符是 b }

B = { w is a subset of {b,d}* such that the last character is b }

人们如何定义这一点?我认为字母表将是两者的结合，使其成为 {a,b,c,d} 但除此之外，我不知道如何对此进行 DFA.

How would one define this? I think the alphabet would be the union of both, making it {a,b,c,d} but aside from that, I wouldn't know how to make a DFA of this.

如果有人能对此有所了解，那就太好了.

If anyone could shed some light on this, that would be great.

推荐答案

从集合论的角度来看，每种语言只是一些字母表上的一组字符串 Σ₁ 和 Σ₂.如果您将两种语言相交，则结果集中唯一可能出现的字符串是那些由 Σ₁ ∩ 中的字符组成的字符串.Σ₂，因为任何不在该集合中的字符都必须完全属于一个集合中的字符串.

From a set-theoretic perspective, each language is just a set of strings over some alphabets Σ₁ and Σ₂. If you intersect two languages, the only strings that can possibly be in the resulting set are those strings that are made of characters in Σ₁ ∩ Σ₂, since any characters not in that set must belong to strings purely in one set.

至于如何为此构建 DFA - 我建议从回答这个问题开始 - 给定任何常规语言 L 超过字母表 Sigma;，您将如何修改该 DFA 以获得语言 Sigma;&杯子;{ x }，其中 x ∉Σ?一种方法是添加一个新的死状态"，并在 Σ 中的所有字符上向自身过渡.&杯子;{ x }，然后在字符 { x } 上添加从 DFA 中的每个状态到死状态的转换.然后，您可以使用它来将 Σ₁ 和 Σ₂ 上的原始语言的 DFA 转换为具有字母 Σ₁ ∪Σ₂.完成此操作后，您可以使用常规算法将两个 DFA 相交来计算它们的交集，从而为两种语言的交集取回 DFA.

As for how to build a DFA for this - I would suggest starting off by answering this question - given any regular language L over alphabet Σ, how would you modify that DFA to have language Σ ∪ { x }, where x ∉ Σ? One way to do this would be to add in a new "dead state" with a transition to itself on all characters in Σ ∪ { x }, then to add a transition from every state in the DFA to the dead state on character { x }. You can then use this to transform the DFAs for the original languages over Σ₁ and Σ₂ to have alphabets Σ₁ ∪ Σ₂. Once you've done that, you can use the normal algorithm for intersecting two DFAs to compute their intesection and thus get back a DFA for the intersection of the two languages.

希望这会有所帮助！

这篇关于两种不同字母的语言的交集是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！