計算定義 2
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/02 21:04 UTC 版)
「プッシュダウン・オートマトン」の記事における「計算定義 2」の解説
任意の入力 w = w 1 w 2 … w m {\displaystyle w=w_{1}w_{2}\dots w_{m}} について、 w i ∈ Σ , m ≥ 0 {\displaystyle w_{i}\in \Sigma ,m\geq 0} であり、M が w を受容するのは、計算経路 ( q 0 , q 1 , . . . . , q n ) {\displaystyle (q_{0},\,q_{1},....,\,q_{n})} と有限の状態列 r 0 , r 1 , r 2 , … , r m ∈ Q , m ≤ n {\displaystyle r_{0},r_{1},r_{2},\dots ,r_{m}\in Q,m\leq n} が存在し、以下が成り立つ場合である。 i = 0 , 1 , 2 , … , m {\displaystyle i=0,1,2,\dots ,m} の各々について、 r i {\displaystyle r_{i}} が計算経路上にある。すなわち、ある f ( i ) {\displaystyle f(i)} が存在し、 i ≤ f ( i ) ≤ n {\displaystyle i\leq f(i)\leq n} で、 r i = q f ( i ) {\displaystyle r_{i}=q_{f(i)}} が成り立つ。 i = 0 , 1 , 2 , … , m − 1 {\displaystyle i=0,1,2,\dots ,m-1} の各々について、 ( q f ( i ) + 1 , b f ( i ) + 1 ) ∈ δ ( r i , w i + 1 , a f ( i ) + 1 ) {\displaystyle (q_{f(i)+1},b_{f(i)+1})\in \delta (r_{i},w_{i+1},a_{f(i)+1})} ここで a f ( i ) + 1 {\displaystyle a_{f(i)+1}} と b f ( i ) + 1 {\displaystyle b_{f(i)+1}} は計算定義 1 で定義されたもの。 q j ∉ { r 0 , r 1 , … r m } {\displaystyle q_{j}\notin \{r_{0},r_{1},\dots r_{m}\}} であるとき、 ( q j + 1 , b j + 1 ) ∈ δ ( q j , ϵ , a j + 1 ) {\displaystyle (q_{j+1},b_{j+1})\in \delta (q_{j},\epsilon ,a_{j+1})} ここで a j + 1 {\displaystyle a_{j+1}} と b j + 1 {\displaystyle b_{j+1}} は計算定義 1 で定義されたもの。 r m = q n {\displaystyle r_{m}=q_{n}} かつ r m ∈ F {\displaystyle r_{m}\in F} これら定義はスタックが空かどうかの判定機構を提供していない点に注意。スタックが空かどうかを判定するには、計算前にスタックに特殊記号を書いておき、PDA がスタックを読んでその記号が読み取れた場合は空であると判断する。形式的には、 δ ( q 0 , ϵ , ϵ ) = { ( q 1 , $ ) } {\displaystyle \delta (q_{0},\epsilon ,\,\epsilon )=\{(q_{1},\$)\}} という遷移を導入する。ここで、$ はその特殊記号である。
※この「計算定義 2」の解説は、「プッシュダウン・オートマトン」の解説の一部です。
「計算定義 2」を含む「プッシュダウン・オートマトン」の記事については、「プッシュダウン・オートマトン」の概要を参照ください。
- 計算定義 2のページへのリンク
