theory - 两种不同字母的语言的交集是什么？

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

8年前关闭。



Improve this question




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

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

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

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

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

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

Answer 1

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

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

希望这有帮助!