0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

有限オートマトンの状態遷移表

Posted at

応用情報技術者平成28年秋期 午前4

次の表は,入力記号の集合が{0,1},状態集合が{a,b,c,d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには,どの状態を受理状態とすればよいか。

image.png

1、表の有限オートマトンを図にする ※これが大事です。

image.png

2、
・ビット列「110」が入力されるときに、a~dのどの状態であるかはわかりませんが、最後の0が入力されて遷移する先はaかcのどちらかしかないですね。

xxc
or
xxa です。

・cが最後とすると
a->(1)->b->(1)->d->(1)->c
。。。
正しいのようですね。

・aが最後とすると
cのみが来るので、且つ0ので、110にはできないですね。

参照:
https://www.ap-siken.com/kakomon/28_aki/q4.html

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?