1

我一直在练习一些关于自动机理论的问题，在那里我遇到了一个关于最小 dfa 的问题，我无法弄清楚我哪里出错了。我在最小 dfa 中得到了 4 个状态，但我的书说答案是 3。问题要求给定的 NFA 转换为最小 DFA 并计算后一个中的状态数。给定的 NFA（p 和 r 分别是初始状态和最终状态）是：

{p}---b-->{q}
{q}---a--->{r}
{q}---b--->{s}
{r}---a--->{r}
{r}---b--->{s}
{s}---a--->{r}
{s}---b--->{s}

我得到 4 个状态：[r]、[p]、[q,s]、[dead]。最终的 [r] 和非最终状态 [q,s] 可以在这里合并，因为它们会导致相似接收输入 a 和 b 的配置？？我了解到最终和非最终状态不能在同一个等价类中......

4

1 回答 1

0

好的，让我们从 DFA 的所有可能状态开始，将有 17 个（4 个符号为 2^4，空集为 1）。这些将是：

{}
{p}
{q}
{r} 
{s}
{p,q}
{p,r}
{p,s} 
{q,r} 
{q,s}
{r,q}
{r,s}
{p,q,r}
{p,q,s}
{p,r,s}
{q,r,s}
{p,q,r,s}

现在我们有了所有可能的集合，让我们突出显示从开始状态p可以到达的所有集合：

{}
{p} --- Start state. From here we can get to {q} only as defined by the transition {p}--b-->{q}
{q} --- from here, we get to r or s, so {r,s} as defined by {q}--a-->{r} and {q}--b-->{s}
{r} 
{s}
{p,q}
{p,r}
{p,s} 
{q,r} 
{q,s}
{r,q}
{r,s} --- from here, we can only get to r or s (the same state!), so we're at a dead end.
{p,q,r}
{p,q,s}
{p,r,s}
{q,r,s}
{p,q,r,s}

因此，三个可访问状态是 {p}、{q} 和 {r,s}。“死”状态或空集不可到达的原因是没有任何可访问的转换导致它。希望这可以帮助！

于 2013-12-14T21:01:49.747 回答