1

CLRS から有限オートマトンとの文字列マッチングを学んでいます。いくつかの演習問題を解いています。演習問題 32.3-1 については、

パターン P = aabab の文字列照合オートマトンを構築し、テキスト文字列 T = aaababaabaababaab に対するその操作を示します。

以下は私の遷移関数です。

states   a   b
 0       1   0
 1       2   0
 2       2   3
 3       4   3
 4       4   5
 5       ?   ?

私の遷移関数は正しいですか? そして、最後の行を埋めるにはどうすればよいですか? どんな助けでも

4

1 に答える 1

1

パターンを含む文字列を受け入れる有限オートマトンを作成していると思いますaabab。

有限オートマトンには 2 つの間違いがあります。

状態3および状態 4 で、

state3の場合、入力が の場合、 statebに戻らなければなりません0。たとえば、パターンaabbは state に強制的に戻します0。ここでは、 state から最初からやり直す必要があります0。

状態4の場合、入力がの場合、パターンがあるためa、状態に戻らなければなりません。たとえば、パターンは state に強制的に戻します。2aaaabaa2

修正された有限オートマトンを以下に示します。

states   a   b
 0       1   0
 1       2   0
 2       2   3
 3       4   0
 4       2   5
 5       5   5

ここで 5 はあなたの Accepting 状態です。文字列に必要なパターンが見つかった場合にのみ、この状態に到達します。パターンが見つかったら、文字列が何であっても受け入れ状態のままです。したがって、入力aとbオンの両方の状態5が5それ自体にとどまります。

遷移関数は、部分文字列 ' aabab ' を含む文字列を受け入れる fa の関数です。1foraおよび0for の状態に戻る場合b、遷移関数は部分文字列 ' aabab ' で終わる文字列を受け入れます。状態 5 のみが受け入れ状態であるとします。

于 2015-08-13T06:59:37.873 に答える