第２章 基礎となる考え方 ２．１ ２．２ ２．３ ２．４ ２．５ オートマトンと状態遷移図 形式言語と自然言語 形式言語のモデル化 言語の理論 プログラムの構成要素 ２．１ オートマトンと状態遷移図 （１）非決定性有限オートマトン （NFA: non-deterministic finite automaton） A(Q, X, δ, q0, F) 【定義】オートマトンA ⇒ Q ： 内部状態の集合 ｛q1, q2, q3, ・ ・ ・, qn｝ X ： 入力記号の集合 ｛x1, x2, x3, ・ ・ ・, xn｝ δ（遷移関数）：S×（X∪｛ε｝）からSのべき集合への関数 q0 ： 初期状態の要素（Qの特定の要素） F ： 最終状態の集合（Qの部分集合） 非決定的で取り扱いが不便なので、実際は決定的有 限オートマトン（DFA: deterministic finite automaton）が 用いられる。 （２）決定的有限オートマトン 【定義】オートマトンA ⇒ Q X Y δ関数 q(t) λ関数 A(Q, X, Y, δ, λ） ： 内部状態の集合 ｛q1, q2, q3, ・ ・ ・, qn｝ ： 入力記号の集合 ｛x1, x2, x3, ・ ・ ・, xn｝ ： 出力記号の集合 ｛y1, y2, y3, ・ ・ ・, yn｝ ： q(t+1)=δ[q(t), x(t)] ： 時刻 t における内部状態 ： y(t+1)=λ[q(t),x(t)] [注]確定オートマトンとも呼ばれる 確定オートマトン 時刻 t における状態 q(t) と入力x(t) に対して 必ず時刻(t+1)の状態q(t+1) と出力y(t+1)が 存在する。 表現方法 ①状態遷移図 ②状態遷移表 ③遷移行列 （３）状態遷移図 【例】 x2/y1 q2 x2/y2 x1/y2 q1 x1/y1 x2/y1 x1/y2 q3 （４）状態遷移表 【例】 q1 q2 q3 x1 (q1, y2) (q3, y1) (q2, y2) x2 (q2, y1) (q2, y2) (q1, y1) （５）状態遷移行列 【例】 q1 q2 q3 q1 x1/y2 0 x2/y1 q2 x2/y1 x2/y2 x1/y2 q3 0 x1/y1 0 【例】 （６）状態行列による表現（１） P0 ( xk ) [ Pi , j ( xk )] (i, j 1, 2, , n, k 1, 2, , m) Pi,j は条件確率⇒有限オートマトンの場合、０または１ q1 q2 q3 q1 q2 x1/y2 x2/y1 0 x2/y2 x2/y1 x1/y2 q3 0 x1/y1 0 【例】 状態行列による表現（２） 1 0 0 0 1 0 P0 ( x1 ) 0 0 1 , P0 ( x2 ) 0 1 0 0 1 0 1 0 0 入力があると確定的に 他の状態に遷移する ことを示す。 q1 q2 q3 q1 q2 x1/y2 x2/y1 0 x2/y2 x2/y1 x1/y2 q3 0 x1/y1 0 （７）確率オートマトン 状態遷移は遷移確率で決まる（確定的でな い） q(t+1) y(t) q(t) q1 q2 ・・ ・ x1 x2 P(x1) P(x2) … xn … P(xn) Y(x1) Y(x2) x1 x2 … xn … Y(xn) qn n P( x) [ p ] x i, j 0 p 1, x i, j p j 1 x i, j 1 状態遷移図と確率行列の例 マルコフ連鎖： ある時刻の状態が次の時刻の状態を確率的に規定する 0.2 0.6 q1 q1 0.8 0.4 x1 x2 0.7 0.3 q2 q2 0.3 0.7 0.2 0.8 P ( x1 ) 0.7 0.3 0.6 0.4 P ( x2 ) 0 .3 0 .7 ある行の列方向に 加算すると１になる ことに注意
© Copyright 2024 ExpyDoc
