情報数理Ⅱ 第10章　オートマトン 平成28年12月21日

本日の学習内容と目的 ＜学習内容＞ ＜目的＞ オートマトンとは 状態遷移表 状態遷移図 オートマトンの概念を理解し、状態遷移表および状態遷移図 を読み取れるようになる。

１．オートマトンとは Automaton：本来の言葉の意味は自動人形。matonはギリシア語の matos（動く）に由来 情報科学では、次のように出力が入力と内部状態に応じて決定される システムを意味する。（Wikipedia） 　外から、連続している情報が入力される 　内部に「状態」を保持する 　外へ、何らかの情報を出力する 元々は、計算する（“考える”と言っても良い）という行為をモデル化し た仮想機械として考案された。

補足）計算可能性とチューリング機械 アラン・チューリング 計算可能性問題に挑む アラン・チューリング　計算可能性問題に挑む 背景：1931年　クルト・ゲーデル　「自然数を扱う数論体系の内部か らは証明できない命題があること」（不完全性定理）を発表　→　数 学界の危機 1934年　アラン・チューリング（22歳）　ケンブリッジ大で研究課題 （ヒルベルトの課題）に取り組む：→　実際には証明不能な課題だっ た。 このとき、計算できない（証明できない）問題とはどういう性質を持 つのか？について根本的に遡って考えた。 それがチューリング機械（1937年）のアイデアにつながる。

計算とはどういう過程？ 2x+3=1 2x=1-3 2x=-2 x=-1 チューリングにならって簡単な例で考えてみる。 ＜ゴール＞ ｘ＝数　となればよい ＜ゴール＞ 2x+3=1 3を右辺へ移項 右辺(1-3)を計算 2x=1-3 2x=-2 両辺を2で割る x=-1 終了！ 式を変形して行き、目的とする式に到達した時点で終了→計算可能 記号を変換（置き換え）する操作が終了したら計算可能

計算不可能とはどうやって判定できる？ 解けない例 2x+y=1 2x=1-y 1-y=2x -y=2x-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 ･･･ Q1 アルゴリズムに対応！ １ B ･･･ Q2 １ B ･･･ Q2 ０ B ･･･ S

オートマトン ここで扱うのは･･･ 有限オートマトン その後、チューリング機械の概念を一般化して、テープの長さやヘッド の移動方向に様々な制限を加えた際の、計算可能な範囲が研究された。 それら（各チューリング機械）はオートマトン（automaton） と総称さ れる様になった。 オートマトン：状態遷移関数によって定義された操作を繰り返す仮想機 械を指す。 状態遷移関数の種類によって色々なオートマトンを定義可能 ここで扱うのは･･･ 有限オートマトン 有限の長さのテープ、ヘッド、有限状態装置から構成 ヘッドは一方向のみ動く

２．状態遷移表 1 A B C B 有限オートマトンの状態遷移を表す表 状態とイベントの対応を与える 例） イベント 状態 有限オートマトンの状態遷移を表す表　 　状態とイベントの対応を与える 例） 1 A B C イベント 状態 B 開始状態をAとして10を入力すると、状態は何になるか？

例題 0 1 1 0 a→a→b→d→c 入力 1 a b c d 状態 【基礎課題10-1】、【基礎課題10-2】 状態a,b,c,ｄに対する入力が1,0である有限オートマトンの状態遷移表は次の通りです。開始状態をaとして、左から順に読み込む場合、0110が受理されるためには、どの状態を受理状態とすればよいですか。 入力 0 1 1 0 1 a b c d a→a→b→d→c 状態

３．状態遷移図 0,1 イベント（事象） 有限オートマトンの遷移を図で表したもの A 1 開始状態 終了状態 B C A 状態 遷移 1 A A B C イベント ３．状態遷移図 状態 有限オートマトンの遷移を図で表したもの 0,1　イベント（事象） A 1 開始状態 終了状態 B C 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

第2回理解度テスト 日時：1月11日　10:55～11:55 出題範囲：第6章～第10章 一切の披見不可