DFA 创建和最小化
DFA creation and minimization
任务：绘制一个 DFA，它接受字母表 {0,1} 中的单词，其中最后一个字符在单词的其他任何地方都不重复。
（示例：单词 0、1、00001、111110、ε 是此 NFA 的语言，而单词 010、111、0010、101 不是）。
我认为我的 DFA 是正确的，但我无法将其最小化，因为我有一个陷阱状态，无论我做什么都无法摆脱。有什么建议或提示吗？
你的 DFA 是正确的（除了初始状态 q0 应该是接受的，因为空字符串在语言中）。它也是最小的；我们可以证明导致每个状态的字符串集都是可区分的 w.r.t。根据 Myhill-Nerode 不可区分关系的语言。
q0: L 中的任何字符串都可以附加到引导此处的字符串（空字符串）以获得 L
中的另一个字符串
q1：将 L 中的字符串 0 附加到 0 得到不在 L 中的 00，因此 q1 与 q0 不同。
q2：将 L 中的字符串 1 附加到 1 得到不在 L 中的 11，因此 q2 与 q0 和 q1 不同（因为将 1 附加到 0 得到的 01 也在 L 中）
导致 q3 的字符串与 q1 不同，因为您不能附加空字符串（即 q1 正在接受而 q3 不是），但其他方面相同，因此 q3 也是不同的来自 q0-q2
导致 q4 的字符串与 q2 不同，因为您不能附加空字符串（即 q2 正在接受而 q4 不是），但其他方面相同，因此 q4 也是不同的来自 q0-q2
将除空字符串以外的任何内容附加到导致 q5 的字符串会导致字符串不在该语言中，因此它不同于 q0-q4
将任何内容附加到导致 q6 的字符串会导致不在该语言中的字符串，因此它与 q0-q5 不同（这些字符串与导致 q5 的字符串的不同之处仅在于您甚至不能将空字符串附加到它们以获得 L 中的字符串，即 q6 不接受而 q5 接受）。
因此，您的 DFA 是最小的。您可以通过尝试 运行 最小化算法并注意没有删除任何状态来证明这一点。
注意：这取决于你的定义，但它是 DFA 的正常（我会说是首选）定义，它们定义了所有转换，这意味着死（或你称之为陷阱）状态需要被显示。最小化算法可能不会删除它们，但您可以根据需要删除它们（尽管我将生成的自动机称为非确定性自动机，因为某些转换未指定确定性行为）。
任务：绘制一个 DFA，它接受字母表 {0,1} 中的单词，其中最后一个字符在单词的其他任何地方都不重复。 （示例：单词 0、1、00001、111110、ε 是此 NFA 的语言，而单词 010、111、0010、101 不是）。
我认为我的 DFA 是正确的，但我无法将其最小化，因为我有一个陷阱状态，无论我做什么都无法摆脱。有什么建议或提示吗？
你的 DFA 是正确的（除了初始状态 q0 应该是接受的，因为空字符串在语言中）。它也是最小的；我们可以证明导致每个状态的字符串集都是可区分的 w.r.t。根据 Myhill-Nerode 不可区分关系的语言。
q0: L 中的任何字符串都可以附加到引导此处的字符串（空字符串）以获得 L
中的另一个字符串q1：将 L 中的字符串 0 附加到 0 得到不在 L 中的 00，因此 q1 与 q0 不同。
q2：将 L 中的字符串 1 附加到 1 得到不在 L 中的 11，因此 q2 与 q0 和 q1 不同（因为将 1 附加到 0 得到的 01 也在 L 中）
导致 q3 的字符串与 q1 不同，因为您不能附加空字符串（即 q1 正在接受而 q3 不是），但其他方面相同，因此 q3 也是不同的来自 q0-q2
导致 q4 的字符串与 q2 不同，因为您不能附加空字符串（即 q2 正在接受而 q4 不是），但其他方面相同，因此 q4 也是不同的来自 q0-q2
将除空字符串以外的任何内容附加到导致 q5 的字符串会导致字符串不在该语言中，因此它不同于 q0-q4
将任何内容附加到导致 q6 的字符串会导致不在该语言中的字符串，因此它与 q0-q5 不同（这些字符串与导致 q5 的字符串的不同之处仅在于您甚至不能将空字符串附加到它们以获得 L 中的字符串，即 q6 不接受而 q5 接受）。
因此，您的 DFA 是最小的。您可以通过尝试 运行 最小化算法并注意没有删除任何状态来证明这一点。
注意：这取决于你的定义，但它是 DFA 的正常（我会说是首选）定义，它们定义了所有转换，这意味着死（或你称之为陷阱）状态需要被显示。最小化算法可能不会删除它们，但您可以根据需要删除它们（尽管我将生成的自动机称为非确定性自动机，因为某些转换未指定确定性行为）。