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}

[r]、[p]、[q、s]、[dead] の 4 つの状態を取得しています。最終状態 [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}

したがって、アクセス可能な 3 つの状態は {p}、{q}、および {r,s} です。「死んだ」状態、または空のセットに到達できない理由は、アクセス可能な遷移のいずれもそれにつながらないためです。お役に立てれば！

于 2013-12-14T21:01:49.747 に答える