regular-language - 这是否是制作 DFA 以接受给定常规语言的前缀语言的一般方法？

Question

可以安全地概括一下，如果给定一个 DFA 说 M ，我们可以获得前缀语言的 DFA（请注意，给定语言的前缀语言由所有字符串 u 组成，使得 uv 是 L 的一个元素v 是 $$ \[\sum\textsuperscript{*}] $$ ) 的一个元素，通过将 M 的所有具有到最终状态的路径的状态添加到新 DFA M' 的最终状态集。这个 M' 将接受 L 的前缀语言。

标签： regular-languageautomata

Answer 1

是的，这个建筑工程。为了正式证明这一点，我们可以争辩说，您新构建的自动机的语言（1）是前缀语言的子集，（2）是前缀语言的超集。也就是说，（1）新自动机语言中的所有内容都是原始自动机语言中字符串的前缀，并且（2）原始语言中字符串的每个前缀都是新自动机语言中的字符串自动机。每当你想证明两个集合相等时，这是一个很好的（但肯定不是唯一的）方法。同样，如果每个集合都是另一个的子集和超集，则两个集合是相等的。我们现在将依次证明这两个必要的主张中的每一个，然后得出期望的结论。

第 1 部分：新自动机语言中的每个字符串都是原始自动机语言中字符串的前缀。假设情况并非如此。也就是说，您的新自动机接受的内容不是原始语言中任何字符串的前缀。然后，新的 DFA 必须有一个接受状态，该状态没有通往原始 DFA 中接受状态之一的路径。但这是一个矛盾，因为通过构造，新 DFA 中的所有接受状态都有通往原始 DFA 中接受状态的路径。因此，我们的假设是错误的，新 DFA 接受的每个字符串都是一个前缀。

第 2 部分：新 DFA 接受原始语言中每个字符串的每个前缀。假设情况并非如此。然后在原始语言中存在字符串 xy 的某些前缀 x，新 DFA 不接受该前缀 x。假设字符串 x 导致原始 DFA 中的状态 q，而字符串 xy 导致原始 DFA 中的状态 q'。因为 xy 是原始语言中的字符串，所以 q' 必须是可接受的。请注意，有一条从 q 到 q' 的路径（从 q 开始并处理后缀 y）。因此，q 在新的 DFA 中必须是接受的，并且由于 x 在原始 DFA 中导致了 q，因此它也在新的 DFA 中导致并且必须被接受。这是一个矛盾，所以必须是所有前缀都被接受的情况。

因为新的 DFA 只接受前缀，并且因为它接受所有前缀，所以我们得出结论，它准确地接受了原始语言的前缀。