「情報科学」(4) データと計算(2) と 有限オートマトン

目次 写像と計算 データ構造の操作 関数から状態遷移へ 有限オートマトン 有限要素の写像・無限の要素間の関係，再帰，メソッド定義 再帰的データ構造の操作 関数から状態遷移へ 繰り返し構文 有限オートマトン

復習: 計算とは写像である 例: m月の日数, 「椿姫」の作曲者, 電話帳, じゃんけんの手がx, yのときの勝者 入力空間 出力空間 入力が組だと考える 例: m月の日数, 「椿姫」の作曲者, 電話帳, じゃんけんの手がx, yのときの勝者 有限個の要素間の関係は表で表せる (cf. 連想メモリ) directory = { "総長" => "21000", "学部長" => "46001", "守衛" => "46666"} Ruby

無限個…コンピュータが扱う整数のようなデータは厳密には有限だが，全ての整数についての関係を書き並べることは難しいので事実上無限 表では表せない写像もある 入力空間 出力空間 入力空間に無限の要素が ある関係も表したい 例: xの自乗，xとyの和，n角形の対角線の数，身長heightで体重weightの人のBMI 無限に大きな表が必要になる 無限の要素を扱う演算が予め用意されているので，それを使えば一部は表せる xの自乗: x*x，xとyの和: x+y 無限の要素を扱う演算を組み合わせれば，さらに多くの関係を表せる 対角線: (n−3)*n/2， 　 BMI: weight/height**2 無限個…コンピュータが扱う整数のようなデータは厳密には有限だが，全ての整数についての関係を書き並べることは難しいので事実上無限

n, height, weightがとり得る値は事実上無限 復習: 計算は関数で表される 関数(メソッド)によって，引数が変化する場合の出力を「式」として書ける 条件分岐などを使うとより複雑な計算が書ける def diagonals(n) (n-3)*n/2 end def bmi(height, weight) weight/height**2 Ruby n, height, weightがとり得る値は事実上無限 n角形の対角線の数 身長heightで体重weightの人のBMI

演算の組み合わせだけでは 表せない計算もある 式の形が固定されていないような計算は，演算の組み合わせだけでは表せない 例: nの階乗 (1×2×…×n) 掛け算だけで計算できるが，掛け算を使う回数は一定ではない コラッツ予想：「ある数が偶数のときは半分に，奇数のときは3倍して1を足す」を繰り返すといずれ1になる 　　　xが1になるまでの繰り返し回数 5→16→8→4→2→1 …5回

再帰: 無限の計算を有限で表す 再帰: ある関数を定義するときに，その関数自身を使って定義すること 例: nの階乗 f(n) は f(n–1)*n 厳密にはn=0のときは別に定義するので f(0) = 1 f(n) = f(n – 1)*n (n > 0のとき) 1 n=0の場合 n>0の場合 n * – f 1 f = の定義

再帰による定義の例(2) コラッツ予想「ある数nが偶数のときは半分に，奇数のときは3倍して1を足す」を繰り返すといずれ1になる nが1になるまでの繰り返し回数c(n) 場合分け＋再帰で定義できる c(1) = 0 (1は0回で1に到達する) c(n) = c(n/2) + 1 (nが偶数のとき) c(n) = c(3*n + 1) + 1 (nが奇数のとき) 未解決問題: 1になることは証明されていない! 例:c(5)の定義は: 5は奇数なので16になる。16から1になる回数をc(16)とするとc(5)=c(16)+1

再帰的な計算を メソッドにする 場合分けされた関数を一つのメソッドにする 場合分けはif then elseを使う Ruby def f(n) if n == 0 1 else f(n-1)*n end def c(n) if n == 1 elsif is_even(n) c(n/2) + 1 c(3*n+1) + 1 場合分けされた関数を一つのメソッドにする 場合分けはif then elseを使う プログラミング言語によっては再帰的な関数を定義するための特別な方法がある(letrec) f(0) = 1 f(n) = f(n–1) * n (n > 0のとき) c(1) = 0 c(n) = c(n/2) + 1 (nが偶数のとき) c(n) = c(3*n+1)+1 (nが奇数のとき)

いろいろ考えてみよう n番目のフィボナッチ数 nCm (n個からm個選ぶ組み合わせ数) k = 1…n の最大のc(k) 素数の判定(nが素数ならtrueとなる関数) 2…nの中の素数の個数 などなど

データ構造に対する計算の例 構造の上を渡り歩く データ構造を作る/作り換える 合計を求める，最大値を求める 整数を素因数分解して素因数のリストを作る 小さい順に整列する 整列されたリストに値を追加する リストの逆順のリストを作る 5 * x ** 2 3 − / y + 1 Expr.new( Expr.new(3, :*, Expr.new(:x, :**, 2)), :-, Expr.new(5, :*, :x)), :/, Expr.new(:y, :+, 1)) 木構造データを作る式の例

再帰的データ構造に対する計算 sum( )  sum( ) + sum( ) sum( )  sum(y) + sum(1) （再帰的）データ構造も整数と同様に値と考えることができる 再帰的な関数によって素直に書けることが多い 例: 整数の木tに現われる数の合計を求めるsum(t) 演算子(*とか/)は無視し，変数は0とみなすことにしよう 木のsum = (左の子のsum)と(右の子のsum)の和になる 場合分けが必要: tが木の場合, 変数の場合, 数の場合… 5 * x ** 2 3 − / y + 1 sum( )  sum( ) + sum( ) sum( )  sum(y) + sum(1) y + 1 sum(y)  0 sum(1)  1

再帰的データ構造に 対する再帰的な計算 def sum(t) if t.kind_of?(Expr) Ruby 再帰的データ構造に 対する再帰的な計算 第2週で 定義した「式」 Expr = Struct.new(:left, :operator, :right) def sum(t) if t.kind_of?(Expr) sum(t.left) + sum(t.right) elsif t.kind_of?(Integer) t else end tの値が構造体Exprのときtrue 再帰 左右のsumの 合計(再帰) tは整数なのでそのまま返す tの値が整数の ときtrue tがそれ以外， つまり変数のときは0

再帰的なデータ構造を扱う関数 木の左右を逆転させる mirror( ) → def mirror(t) 5 * x ** 2 3 − / y + 1 5 * x ** 2 3 − / y + 1 mirror( ) → def mirror(t) if t.kind_of?(Expr) Expr.new(mirror(t.right), t.operator, mirror(t.left)) else t end 再帰的に子を反転させる 新しくノードを作るのがミソ Ruby

いろいろ考えてみよう 木の「大きさ」を求める関数 (ノード，変数，数を「1個」と数える) 木の中の変数を数に置き換える関数 変数の無い木を「計算」する関数 木を文字列にする関数 5 * x ** 2 3 − / y + 1 5 * 8 ** 2 3 − / y + 1 subst(:x,8, 　　　) → 5 * x ** 2 3 − / y + 1 string( 　　　　　　) →"(((3*(x**2))-(5*x))/(y+1))"

関数の計算過程 計算 = 式の書き換え という考え方 計算 = 状態の変更 という考え方 計算 = 式の書き換え　という考え方 方針: 式の中で計算できる演算があったら，そこを結果で置きかえる 　　　　関数が使われていたら，関数の定義をそこに展開し，変数を 　　　　　　引数で置きかえる 特徴：手で計算する方法に近い 　　　　どこを書き換えるかが難しい 　　　　無駄な計算が生じる場合がある 計算 = 状態の変更　という考え方 方針: 変数の値を書き換えてゆくことで計算が進行 　　　　関数呼出は，現在の計算状態(変数の値)を退避して関数の中 　　　　　　を実行 特徴：実際のプログラミング言語の実行方式 　　　　無駄が少ない

式の書き換えによる計算過程 f(n)  if n=0 then 1 else f(n−1)*n f(3) if 3=0 then 1 else f(3-1)*3 f(2)*3 (if 2=0 then 1 else f(2-1)*2)*3 (f(1)*2)*3 ((if 1=0 then 1 else f(1-1)*1)*2)*3 ((f(0)*1)*2)*3 (((if 0=0 then 1 else f(0-1)*0)*1)*2)*3 (((1)*1)*2)*3 ((1)*2)*3 (2)*3 6 計算できる部分式を結果に書き換え 関数は関数の定義に書き換える その際，変数を引数で置きかえ 書き換えできる場所がなくなったら終了 f(n)  if n=0 then 1 else f(n−1)*n

計算 = 状態の変更 def f(n) if n == 0 現在のnを退避して新たにn=2とする 1 → f(3)の計算: n=3とする else f(n-1)*n end 現在のnを退避して新たにn=2とする → f(3)の計算: n=3とする if 文を実行 f(n−1)*nを実行 ← 2*3=6を返す → f(2)の計算: n=2とする if 文を実行 f(n−1)*nを実行 ← 1*2=2を返す どこを実行中か覚えておく → f(1)の計算: n=1とする if 文を実行 f(n−1)*nを実行 ← 1*1=1を返す 覚えておいた場所から再開 → f(0)の計算: n=0とする if 文を実行 ← 1を返す nの値を復活させるのでn=3

関数から状態遷移へ: 関数の定義のバリエーション 関数から状態遷移へ: 関数の定義のバリエーション 一つの値を求める関数にも色々な定義がある 例:　nの階乗 f(n) f(n) = f '(n,n) f '(1,g)=g f '(k,g)=f '(k−1,(k−1)*g) f(n) = f ''(0,1,n) f ''(n,g,n)=g f ''(k,g,n)=f ''(k+1,(k+1)*g,n) 補助関数f '(k,g)は 1*2*…*(k−1)*gを求める関数 補助関数f ''(k,g,n)はg*(k+1)*(k+2)*…*nを求める関数

fの値に手を加えている→末尾再帰ではない 関数から状態遷移へ: 末尾再帰 関数の定義が，別の関数に丸投げしているようなものを末尾再帰という f(n) = f'(n,n) f '(1,g)=g f '(k,g)=f '(k−1,(k−1)*g) f 'に丸投げ→末尾再帰 f(0) = 1 f(n) = f(n – 1)*n (n > 0のとき) fの値に手を加えている→末尾再帰ではない

関数から状態遷移へ: 状態遷移による計算 状態遷移による計算: 状態を刻一刻変化させてゆき，最終的に求める値に到るやり方 関数から状態遷移へ: 状態遷移による計算 状態遷移による計算: 状態を刻一刻変化させてゆき，最終的に求める値に到るやり方 状態: 変数と値の結びつき全体 状態は時間で変化 メモリの内容を状態と思うと，コンピュータの基本的な動作 ある種の関数(末尾再帰的な関数)の計算過程は，状態を変化させてゆくものとも見倣せる f(n) = f '(n,n) f '(1,g)=g f '(k,g)=f'(k−1,(k−1)*g) k g 4 3 12 2 24 1 f(4) → f'(4,4) → f'(4−1,(4−1)*4) → f'(3,12) → f'(3−1,(3−1)*12) → f'(2,24) → f'(2−1, (2−1)*24) → f'(1,24) → 24 状態の時間変化

状態遷移による計算の定義方法 考えるべきこと: 計算過程: 例: nの階乗 状態: 値の組 初期値: 計算を始めるときの状態 状態: 値の組 初期値: 計算を始めるときの状態 遷移: 繰り返し1回ごとの状態の変化させ方 終了条件: 繰り返しを止める条件と，最終的な解 計算過程: 初期値から終了条件が成り立つまで状態を遷移させる 終了条件が成り立ったら終わり 例: nの階乗 状態: (k,gk) の組 ただし gk=k*(k+1)*…*n のような値 初期値: (n,n) 遷移: (k,gk)→(k−1, (k−1)*gk) 終了条件: k=1になったらそのときのgkが解

状態遷移を使ったプログラム [状態](k,gk) の組 [初期値] (n,n) [遷移] (k,gk)→ (k−1, (k−1)*gk) Ruby 状態遷移を使ったプログラム 状態のために変数を用意 [状態](k,gk) の組 [初期値] (n,n) [遷移] (k,gk)→ (k−1, (k−1)*gk) [終了条件] k=1 (そのときのgkが解) 初期値をセット def f_state(n) k=n g=n while k>1 g = g * (k-1) k = k-1 end g 「k>1の間，end までを繰り返せ」という構文 k>1でなくなった; i.e., k=1のとき 状態の変化 (順序に注意)

繰り返し構文 while文 ―― 条件が成り立っている間の繰り返し for文(DO文) ―― 決められた回数の繰り返し Ruby 繰り返し構文 while文 ―― 条件が成り立っている間の繰り返し 式がtrueである間， 「何か」を計算 まず条件をチェックする バリエーション: まず「何か」を 計算するもの(repeat until) for文(DO文) ―― 決められた回数の繰り返し iをx, x+1, x+2, …, yと 変えて「何か」を計算 whileでも実現できる while 式 何か end for i in x..y 何か end

状態遷移による計算の定義例 コラッツ予想 def c_state(n) c(1) = 0 k=n c(n) = c(n/2) + 1 (nが偶数のとき) c(n) = c(3*n+1)+1 (nが奇数のとき) def c_state(n) k=n c=1 while k>1 if is_even(k) k=k/2 else k=k*3+1 end c=c+1 c [状態](k,ck) の組 [初期値] (n,0) [遷移] (k,ck)→ if kが偶数 then (k/2, ck+1) else (k*3+1, ck+1) [終了条件] k=1 (そのときのckが解) kに至るまでがck回

不変量 繰り返しの間，変化しない式のこと 繰り返しの正しさを考える際に必要 例: nの階乗の計算の場合 X(k,g)=(g*(k–1の階乗))=n!で不変 k,gの繰り返し1回の後の値をk',g'とする(プログラムからg'=g*(k–1), k'=k–1) X(k',g') = g' * (k'–1の階乗) = g*(k–1)*(k–2の階乗) = g*(k–1の階乗) = X(k,g) X(n,n)=nの階乗なのでk=1のときのgはnの階乗 def f_state(n) k=n g=n while k>1 g = g * (k-1) k = k-1 end g

考えてみよう 状態・初期値・遷移・終了条件は何か? 状態遷移を使って関数の定義を書き直してみよう 不変量は何か? n番目のフィボナッチ数 nCm (n個からm個選ぶ組み合わせ数) k = 1…n の最大のc(k) 「ある数が偶数のときは半分に，奇数のときは3倍して1を足す」を繰り返すといずれ1になるとしたとき，nが1になるまでに現われた数の最大値 素数の判定(nが素数ならtrueとなる関数) 1…nの中の素数の個数 などなど

繰り返しとデータ構造 大きさが一定のデータ構造(e.g.,配列)に対する計算は，繰り返し構文で記述するのが自然 例: 行列・ベクトルに対する演算 文字列(=文字の配列)検索 表形式データの整列 (次週)

繰り返しの例: ベクトル演算 n次ベクトルは大きさnの数値配列で表せる の計算 ベクトルvのスカラー倍 結果をしまう 配列を作り Ruby 繰り返しの例: ベクトル演算 n次ベクトルは大きさnの数値配列で表せる ベクトルvのスカラー倍 結果をしまう 配列を作り def vector_scale(s, v) w=Array.new() for i in 0..(v.size-1) w[i] = s * v[i] end w def vector_add(v1, v2) for i in 0..(v1.size-1) w[i] = v1[i] + v2[i] $x = [ 1.0, 0.0, 0.0 ] $y = [ 0.0, 1.0, 0.0 ] $z = [ 0.0, 0.0, 1.0 ] vector_add( $x, vector_scale( 2.0, vector_add($y, $z))) vの各要素に ついて スカラー倍した 値をセット の計算 ベクトルの和

繰り返しの例: 文字列の検索 例: 配列sの中で配列pと一致する部分は何番目? Ruby 繰り返しの例: 文字列の検索 例: 配列sの中で配列pと一致する部分は何番目? find( "uraniwaniwaniwaniwatorigairu", "waniwaniwato") → 9 uraniwaniwaniwaniwatorigairu waniwaniwato 2重の繰り返し

繰り返しの例: 文字列の検索 例: 配列sの中で配列pと一致する部分は何番目? sのi番目からとpが一致するか? 状態: pの添字 Ruby 繰り返しの例: 文字列の検索 例: 配列sの中で配列pと一致する部分は何番目? sのi番目からとpが一致するか? 状態: pの添字 def match_at(s, p, i) j = 0 while j < p.size && s[i+j] == p[j] j = j + 1 end j == p.size def find(s, p) i = 0 while !match_at(s, p, i) i = i + 1 i 条件: jがpの終わりまで 到達するかsの(i+j)番目と pのj番目が一致しない 遷移: jを増やす jがpの終わりまで 到達していたら一致 pはsの何文字目から出現するか? find("uraniwaniwaniwaniwatorigairu","waniwaniwato") 簡単のため，最初の出現だけを 見つける。また必ず見つかると仮定

有限オートマトン 状態遷移による計算は，計算が状態空間を移動してゆくものと考えられる 有限オートマトンに対応 → 数理的なモデル 状態空間 f'(4,4) →f'(3,12) → f'(2,24) →f'(1,24) → 24

有限オートマトン 有限個の状態 入力文字列 状態遷移 現在の状態 初期状態 受理状態 有限個の文字：アルファベット 入力文字と現在の状態に従って， 現在の状態を変える

状態遷移図 二進数を，0と1から 成る文字列として入力し， 3の余りを計算する 有限オートマトン 初期状態 1 1 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

011101 初期状態 1 1 1 2 1

1 2 状態遷移図 状態の 番号付け 二進数を，0と1から 成る文字列として入力し， 初期状態 3の余りを計算する 有限オートマトン 1 1 初期状態 1 1 1 1 2

オートマトンの実装 $automaton = [[0,1], [2,0], [1,2]] Ruby オートマトンの実装 $automaton = [[0,1], [2,0], [1,2]] def make_transitions(input) s = 0 for i in 0..(input.size - 1) c = input[i] - ?0 s = $automaton[s][c] end s ?0で0の文字コードの数値が返る ここでは0と1の入力文字しかないのでcは0か1 make_transitions("011001") make_transitions("011011") make_transitions("011101")

$automaton = [[0,1], [2,0], [1,2]] s==0 011101 初期状態 1 1 1 2 1

011101 1 2 $automaton = [[0,1], [2,0], [1,2]] s==0 i==0 c==0 初期状態 1 1 初期状態 i==0 c==0 1 1 1 2 1

$automaton = [[0,1], [2,0], [1,2]] s==0 011101 初期状態 1 1 1 2 1

011101 1 2 $automaton = [[0,1], [2,0], [1,2]] s==0 i==1 c==1 初期状態 1 1 初期状態 i==1 c==1 1 1 1 2 1

$automaton = [[0,1], [2,0], [1,2]] s==1 011101 初期状態 1 1 1 2 1

011101 1 2 $automaton = [[0,1], [2,0], [1,2]] s==1 i==2 c==1 初期状態 1 1 初期状態 i==2 c==1 1 1 1 2 1

$automaton = [[0,1], [2,0], [1,2]] s==0 011101 初期状態 1 1 1 2 1

011101 1 2 $automaton = [[0,1], [2,0], [1,2]] s==0 i==3 c==1 初期状態 1 1 初期状態 i==3 c==1 1 1 1 2 1

$automaton = [[0,1], [2,0], [1,2]] s==1 011101 初期状態 1 1 1 2 1

011101 1 2 $automaton = [[0,1], [2,0], [1,2]] s==1 i==4 c==0 初期状態 1 1 初期状態 i==4 c==0 1 1 1 2 1

$automaton = [[0,1], [2,0], [1,2]] s==2 011101 初期状態 1 1 1 2 1

011101 1 2 $automaton = [[0,1], [2,0], [1,2]] s==2 i==5 c==1 初期状態 1 1 初期状態 i==5 c==1 1 1 1 2 1

$automaton = [[0,1], [2,0], [1,2]] s==2 011101 初期状態 1 1 1 2 1

言語 アルファベット 文字列（語） 言語（形式言語） 有限個の文字の集合 Σなどで表す 例：Σ= {0,1} Σなどで表す　　例：Σ= {0,1} 文字列（語） アルファベットに属する文字の有限列 例：0, 00, 1100, 0101 空列も文字列　εやλで表す 文字列の全体をΣ* で表す　（Kleene閉包） 言語（形式言語） 文字列の集合，すなわちΣ* の部分集合 例：3で割り切れる二進数の全体

言語の認識装置としての 有限オートマトン 状態のいくつかを受理状態とする 与えられた文字列に従って，初期状態から始めて状態遷移を繰り返す 受理状態は複数あってもよい 与えられた文字列に従って，初期状態から始めて状態遷移を繰り返す 初期状態は一つ 文字列を読み終わった直後の状態が受理状態ならば，その文字列を受理 有限オートマトンMが受理する文字列の全体をL(M)と書く。 L(M)をMの受理言語という。

有限オートマトン 3で割り切れる二進数の 全体を受理する 有限オートマトン 初期状態 受理状態でもある。 1 1 1

オートマトンの実装 $final = 0 def accept(input) s = make_transitions(input) Ruby オートマトンの実装 $final = 0 def accept(input) s = make_transitions(input) s == $final end accept("011001") accept("011011") accept("011101") 受理状態は複数あってもよいので，上のコードは不十分 受理状態が複数ある場合に対処せよ（演習）

有限オートマトン 初期状態 0と1を 奇数個ずつ 含む文字列を 受理する オートマトン 1 1 1 1

正則表現(または正規表現） 言語を表す記法 文字列のパターンを表す 例：0(10)*1 例：0(11+00)1 例：0(11+00)*1 0で始まり10が繰り返されて1で終わる文字列 そういう文字列からなる言語 例：0(11+00)1 0の次に11または00が来て，1で終わる文字列 例：0(11+00)*1 この意味を考えなさい

正則表現から有限オートマトンへ 正則表現⇒有限オートマトン 決定化 最小化 実は，有限オートマトン⇔正則表現 任意の正則表現に対して，その言語を受理する非決定的な有限オートマトンが存在する 決定化 非決定的な有限オートマトンは，受理言語が同じ決定的なオートマトンに変換できる。 最小化 決定的なオートマトンは，受理言語をかえずに状態数が最小化できる。 実は，有限オートマトン⇔正則表現 正則言語：正則表現で記述できる言語 　　　　　　　　　　　＝　有限オートマトンで受理できる言語

非決定的な有限オートマトン ε遷移： 文字を入力せずに 遷移できる ε 初期状態 1 1 1 ε 0(11+00)*1を受理する

非決定的な有限オートマトン 受理状態に至る遷移のしかたが 一つでもあればよい。 初期状態 1 1 1 1 1

決定的な有限オートマトン 初期状態 1 1 1

決定的な有限オートマトン 初期状態 1 1 1 1 1 1

状態数最小の有限オートマトン 初期状態 1 1 1 1 1

状態数最小の有限オートマトン 1 2 初期状態 1 3 1 1 1 4 1

オートマトンの実装 実はRubyでは... $automaton = [[1,4], [2,3], [1,4], [4,1], [4,4]] $final = 3 accept("01100111") accept("0110111") 正則表現は /^ と $/ で囲む 構文は説明と少し異なる 実はRubyでは... 文字列が正則表現に属するか？ /^0(11|00)*1$/ =~ "01100111" /^0(11|00)*1$/ =~ "0110111"

有限オートマトンの性質 正則言語の合併，交わり，補集合，連接，Kleene閉包などに関して閉じている たとえば，合併に関しては，任意のM1とM2に対して， L(M1)∪L(M2)=L(M)となるMが存在することが証明できる 二つのオートマトンが受理する言語が同じかどうかを判定することができる しかし，数を数えられない：有限オートマトンの限界 例えば，0と1を同じ数だけ含む文字列のみを受理する有限オートマトンは存在しない