finite-automata - 决定 L(M) = {a} 还是 L(M) =/= {a} 的算法

Question

我开始了解 NFA 和 DFA，并在 Berkley PDF 中的一个关于 DFA 的网上偶然发现了这个问题，但这个问题没有附加解决方案。

我如何能够证明存在一种算法，它接收字母表上的 DFA M 作为输入{a, b}并决定是否L(M) = {a}或L(M) =/= {a}？

任何指导将不胜感激。

Answer 1

给定两个 DFA D1 和 D2，可以通过最小化每个 DFA 并检查生成的 DFA 是否相同来确定 L(D1) = L(D2) （这是因为对于每种语言，都有一个唯一的最小状态 DFA）语）。

现在，您正在尝试检查 L(D1) = {a} 是否。作为提示，你能构造一个语言正好是 {a} 的 DFA 吗？如果是这样，你能用上面的算法来解决这个问题吗？

希望这可以帮助！