regular-language - 证明以下语言是正则的：

Question

令 L1、L2 为正则语言。令 A1=〈Σ,Q,q0,1,F1), A2=〈Σ,P,p0,2,F2) 是它们的 DFA。

通过为其制作适当的 NFA 来证明以下语言是正则的：

3={11′22′…′|12…∈1,1′2′…′∈2}（意思是所有单词的语言，其中偶数位置（从0开始）的字母来自L1和奇数位置上的字母来自 L2。

将不胜感激帮助。谢谢你。

标签： regular-languageautomatadfanfa

Answer 1

考虑以下自动机：

• 字母Σ
• 状态集 (Q x P) 联合 (P x Q)
• 初始状态 (q0, p0)
• 最终状态 (f1, f2)，其中 f1 和 f2 分别在 F1 和 F2 中
• 如果 1 将 q 带到 s 上的 q'，则在符号 s 上采用 (q, p) 到 (p, q') 的转换函数，并且如果 A2 在符号 s 上采用 (p, q) 到 (q, p')符号 s 上的 p 到 p'。

假设你在 L3 中有一个单词 w。我们的机器能接受吗？序列 1, 2, ..., n 将导致自动机到达的状态的第一个分量与 A1 仅处理此序列时 A1 将到达的状态相同。因为 L3 说 w 中的这个序列是 L1 中的一个词，所以状态应该在 A1 中接受，所以第一个组件在 F1 中。类似地，序列 1', 2', ..., n' 是 L2 中的一个字符串，因此它到达的状态是接受。因此，这个 NFA 达到的状态是 (f1, f2) 的形式，因此字符串被接受，因为它必须是。我们刚刚争论过 NFA至少接受这种语言的字符串。剩下的就是争辩说它不接受其他任何东西。

幸运的是，论证的其余部分是直截了当的，我们可能可以在做上述论证的同时做到这一点。它遵循相同的格式。假设我们的 NFA 到达接受状态之一。然后是 (f1, f2) 的形式。这意味着我们看到了一个偶数长度的字符串，其中奇数索引符号一起导致 A1 中的 f1，偶数索引符号导致 A2 中的 f2。但这意味着序列在它们各自的自动机中接受，因此在我们的机器中导致我们进入接受状态的字符串必须是 L3 中的一个单词。我们刚刚论证了 NFA最多接受这种语言的字符串。

由于我们的机器至少接受我们需要的字符串，并且最多接受我们需要的字符串，因此它完全接受我们需要的字符串。