ポスターのPDFファイル - Sendai Logic Group

オートマトンとは?
オートマトンとは
問題
オートマトンとは, 数学的に定義された計算機の模型のひとつです.
オートマトンは文字列を 1 文字ずつ読み込んで, 次にどのような動きを
するかを決めます.
オートマトンは図を用いて次のように表わすことができます.
[問 1]. 下のオートマトンで受理される文字列はどれですか (複数解答可).
0, 3, 6, 9
1, 2, 3, 4,
6, 7, 8, 9
q0
q0
1, 4, 7
1, 2, 3, 4,
6, 7, 8, 9
q1
0, 5
0, 3,
6, 9
0, 5
2, 5, 8
図 2: 初期状態
2, 5, 8
2, 5, 8
q1
0, 3,
6, 9
q2
1, 4, 7
図 1.
q0
1, 4, 7
q0
図 3: 最終状態
図 1 において, q0, q1 のことを状態といいます. オートマトンの状態は有
限個でなければいけません. 二重線の矢印で初期状態を表わし, 二重丸
で最終状態を表わします.
文字列 w の最後の文字を読み取ったとき, オートマトンが最終状態に
なっていれば, w はそのオートマトンに受理されるといいます.
状態の間の矢印は, 状態の変化を表わします. たとえば図 1 では, 状態が
q0 のときは, 0 か 5 を読み込んだら状態は変化せず, それ以外では q1 に変
化するということを表します. 一方, 状態が q1 のときは, 0 か 5 を読み込
んだら q0 に変化し, それ以外では状態は変化しません.
たとえば図 1 のオートマトンに, 35740 という文字列を読み込ませてみ
ると, どうなるでしょうか.
初期状態: q0 / 3 を読み込み, 状態を q1 に
(a) 3
(e) 40
(b) 8
(f) 38
(c) 81
(g) 33333333
(d) 27
[問 2] 下の図は, 2 進数表記の 4 の倍数を受理するオートマトンです. 4 の
倍数は, 2 進数で表わすと下 2 桁が 0 になります.
0
0
q0
q1
q2
1
1
1
0
では, 下の図に適切な矢印を書き加えて, 下 2 桁が 01 で終わるような 2 進
数を受理するオートマトンを完成させてください.
0
q0
1
q1
q2
現在の状態: q1 / 5 を読み込み, 状態を q0 に
現在の状態: q0 / 7 を読み込み, 状態を q1 に
現在の状態: q1 / 4 を読み込み, 状態を q1 に
1
現在の状態: q1 / 0 を読み込み, 状態を q0 に
という要領で状態が変化します (指で追ってみましょう). このことから,
このオートマトンは, 35740 という文字列を受理します.
それでは次に, 1234567 という文字列はどうでしょうか. 実はこの文字
列は受理されません. 一般に, 図 1 で定義されたオートマトンは, (10 進
数表記における)5 の倍数を表わす文字列を受理します.
[問 3] 10 進数表記で, 4 の倍数を受理するオートマトンを考えてください.
(ヒント: 4 の倍数の判定法は?)
計算可能性理論
上で見たようにオートマトンは, 3 の倍数や, 5 の倍数を判定することができます. しかし, オートマトンには判定できないこともあります.
たとえば, 10, 1100, 111000, . . . をすべて受理するようなオートマトンは存在しません (理由を考えてみてください).
そこで, より強力な計算機の模型として, チューリングマシンと呼ばれるものがあります. チューリングマシンは, イギリスの数学者アラン・
チューリングが考案したものです.
現在のコンピュータは, このチューリングマシンが基礎となって実現したものです.
コンピュータで判定できることと, チューリングマシンで判定できるということは同じことです.
チューリングマシンでは, 上記の 10, 1100, 111000, . . . を受理することができます.
ところが, チューリングマシンにも判定できないようなこともあります.
したがって, コンピュータには判定できないようなことがらがあるということがわかります.
「どのようなことがらがコンピュータを使って判定することができるか」を研究する分野を計算可能性理論と言います.
1/1

Download Report