可以安全地概括一下，如果我们给定一个 DFA M ，我们可以获得前缀语言的 DFA （请注意，给定语言的前缀语言由所有字符串 u 组成，使得 uv 是一个元素L 和 v 是 $$ \[\sum extsuperscript{*}] 的元素 $$ ）通过将所有具有到达最终状态路径的 M 状态添加到新 DFA M' 的最终状态集合中。这个 M' 将接受 L 的前缀语言。
是的，这个建筑有效。为了正式证明这一点，我们可以认为新构建的自动机的语言 (1) 是前缀语言的子集，(2) 是前缀语言的超集。也就是说，(1) 新自动机语言中的所有内容都是原始自动机语言中字符串的前缀，并且 (2) 原始语言中字符串的每个前缀都是新自动机语言中的字符串自动机。每当您想证明两个集合相等时，这是一个很好的（但肯定不是唯一的）方法。同样，如果两个集合都是另一个集合的子集和超集，则它们相等。我们现在将依次证明两个必要的主张，然后得出期望的结论。
第 1 部分：新自动机语言中的每个字符串都是原始自动机语言中字符串的前缀。假设情况并非如此。也就是说，您的新自动机接受的内容不是原始语言中任何字符串的前缀。然后，新的 DFA 必须具有一个接受状态，该状态没有到达原始 DFA 中接受的状态之一的路径。但这是一个矛盾，因为通过构造，新 DFA 中的所有接受状态都有一条通向原始 DFA 中的接受状态的路径。因此，我们的假设是错误的，新 DFA 接受的每个字符串都是前缀。
第 2 部分：新 DFA 接受原始语言中每个字符串的每个前缀。假设情况并非如此。然后，原始语言中的字符串 xy 的某些前缀 x 不被新 DFA 接受。假设字符串 x 导致原始 DFA 中的状态 q，字符串 xy 导致原始 DFA 中的状态 q'。因为 xy 是原始语言中的字符串，所以 q' 必须接受。请注意，有一条从 q 到 q' 的路径（以 q 开始并处理后缀 y）。因此，q 在新的 DFA 中必须接受，并且由于 x 在原始 DFA 中导致 q，因此它在新的 DFA 中也导致 q 并且必须被接受。这是一个矛盾，所以一定是所有前缀都被接受的情况。
因为新的 DFA 只接受前缀，并且因为它接受所有前缀，所以我们得出结论，它完全接受原始语言的前缀。
tuliskan sebuah 公式 ekspresi 调节器 dan jelaskan bahasa apa yang dikenali oleh 公式 tersebut