生成DFA的转换表

Question

如何将此NFA转换为DFA：

​

​

从'a‘上的状态BC不会到达任何状态，因此它不会形成DFA

Answer 1

在你的图片中，有一点不清楚哪些州正在接受。如果所有的状态都是可接受的，我们可以写下一个简单的DFA，其中一个状态是等价的。所以，为了便于讨论，我们假设这些状态中可能只有一些是接受的。

因为A是开始状态，所以我们知道对于字母表中的每个符号，我们需要从状态{A}转换。我们发现{A} --a--> {A，B，C}，{A} --b--> {B，C}和{A} --c--> {C}。我们必须在我们的DFA中引入三个新的状态- {A，B，C}，{B，C}和{C} -我们也需要这些状态的转换。

对于{A，B，C}，我们找到{A，B，C} --a--> {A，B，C}，{A，B，C} --b--> {B，C}和{A，B，C} --c--> {C}。这些状态已经在我们的待办事项列表中，所以我们可以继续。

对于{B，C}，我们找到{B，C} --a--> {}，{B，C} --b--> {B，C}和{B，C} --c--> {C}。我们引入了一个对应于空集的新状态，因此我们将其放在待办事项列表中。

对于{C}，我们找到{C} --a--> {}，{C} --b--> {}和{C} --c--> {C}。没有引入新的状态。

最后，很明显，{} --a--> {}，{} --b--> {}和{} --c--> {}。

我们可以写下转换表，如下所示：

q            s    q'
-------------------------
{A}          a    {A,B,C}
{A}          b    {B,C}
{A}          c    {C}
{A,B,C}      a    {A,B,C}
{A,B,C}      b    {B,C}
{A,B,C}      c    {C}
{B,C}        a    {}
{B,C}        b    {B,C}
{B,C}        c    {C}
{C}          a    {}
{C}          b    {}
{C}          c    {C}
{}           a    {}
{}           b    {}
{}           c    {}

根据原始NFA中接受的状态，这组状态可能不是最小的，但您可以很容易地根据接受的状态将其最小化。