スライド

平成27年12月23日
＜学習内容＞
1. オートマトンとは
2. 状態遷移表
3. 状態遷移図
＜目的＞
オートマトンの概念を理解し、状態遷移表および状態遷移図
を読み取れるようになる。
 Automaton：本来の言葉の意味は自動人形。matonはギリシア語の
matos（動く）に由来
 情報科学では、次のように出力が入力と内部状態に応じて決定される
システムを意味する。（Wikipedia）

外から、連続している情報が入力される

内部に「状態」を保持する

外へ、何らかの情報を出力する
 元々は、計算する（“考える”と言っても良い）という行為をモデル化し
た仮想機械として考案された。
アラン・チューリング
計算可能性問題に挑む
 背景：1931年
クルト・ゲーデル「自然数を扱う数論体系の内部か
らは証明できない命題があること」（不完全性定理）を発表 → 数
学界の危機
 1934年
アラン・チューリング（22歳）ケンブリッジ大で研究課題
（ヒルベルトの課題）に取り組む：→ 実際には証明不能な課題だっ
た。
 このとき、計算できない（証明できない）問題とはどういう性質を持
つのか？について根本的に遡って考えた。
 それがチューリング機械（1937年）のアイデアにつながる。
チューリングにならって簡単な例で考えてみる。
問題）
2x+3=1 を満たすｘを求めよ。
2x+3=1
3を右辺へ移項
2x=1-3
右辺(1-3)を計算
2x=-2
両辺を2で割る
x=-1
＜ゴール＞
ｘ＝数となればよい
終了！
式を変形して行き、目的とする式に到達した時点で終了→計算可能
記号を変換（置き換え）する操作が終了したら計算可能
解けない例
問題）
2x+ｙ=1 を満たすｘを求めよ。
＜ゴール＞
ｘ＝数となればよい
2x+y=1
yを右辺へ移項
2x=1-y
(1-y)を計算・・・？→ 両辺を入れ替える
1-y=2x
1を右辺に移項
-y=2x-1
(2x-1)を計算・・・？→ -1を左辺に移項
・・・
永遠に終わらない
記号を変換（置き換え）する操作が終了しない→計算不能！
計算過程を機械的に行い終了するかどうかを判定すれば良い。
計算過程を忠実に行う（必要最小限の）機械を考えた。→
えた仮想機械で実在の機械ではない。
頭の中で考
 テープ、ヘッド、有限状態制御部
テープ →
ヘッド
制御部

→
記憶装置
入出力装置
→ CPU
チューリング機械の動作
①ヘッドが見ている記号を書き換える
②ヘッドを左に動かす
③ヘッドを右に動かす
④計算を終了する
 記号”1”を記号”0”に置き換える
 有限状態制御部の規則（状態遷移関数）
(Q1,1)=(Q2,1,R)
(Q2,B)=(Q2,B,L) アルゴリズムに対応！
(Q2,1)=(S,0,R)
Q1,Q2,S：状態
1,0,B：テープの記号
R,L：ヘッドの移動
０ B B ･･･
S
１ B B ･･･
Q2
１ B B ･･･
Q1
１ B B ･･･
Q2
 その後、チューリング機械の概念を一般化して、テープの長さやヘッド
の移動方向に様々な制限を加えた際の、計算可能な範囲が研究された。
 それら（各チューリング機械）はオートマトン（automaton）と総称さ
れる様になった。
 オートマトン：状態遷移関数によって定義された操作を繰り返す仮想機
械を指す。
 状態遷移関数の種類によって色々なオートマトンを定義可能
ここで扱うのは･･･
有限オートマトン


有限の長さのテープ、ヘッド、有限状態装置から構成
ヘッドは一方向のみ動く
 有限オートマトンの状態遷移を表す表
状態とイベントの対応を与える
 例）
状態
A(1) → B(0) → B
イベント
1
0
A
B
C
B
A
C
C
B
B
開始状態をAとして10を入力すると、状態は何になるか？
【基礎課題10-1】、【基礎課題10-2】
状態a,b,c,ｄに対する入力が1,0である有限オートマトンの状態遷移表は
次の通りです。開始状態をaとして、左から順に読み込む場合、0110が
受理されるためには、どの状態を受理状態とすればよいですか。
a
b
c
d
0
a
c
a
c
1
b
d
b
d
入力
0 1 1 0
状態
a→a→b→d→c
イベント
1
0
A
B
C
B
A
B
C
C
B
状態
 有限オートマトンの遷移を図で表したもの
0,1 イベント（事象）
A
開始状態
1
1
0
1
B
C
0
0
終了状態
A
状態
遷移
【基礎課題10-3】～【基礎課題10-6】
 次に示す有限オートマトンが受理する入力列はどれか。ここで、S1は
初期状態を、S3は受理状態を表している。（平成21年度春）
ア 1011
イ 1100
ウ 1101
エ 1110
1011:
S1(1)→S2(0)→S2(1)→S1(1)→S2
1100:
S1(1)→S2(1)→S1(0)→S3(0)→S2
1101:
S1(1)→S2(1)→S1(0)→S3(1)→S3
1110:
S1(1)→S2(1)→S1(1)→S2(0)→S2
10:55～11:55
 出題範囲：第6章～第10章
 一切の披見不可
 日時：1月13日

Download Report