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

Question

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

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

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

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

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

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

Answer 1

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

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

希望这可以帮助！