計算定義 1
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/02 21:04 UTC 版)
「プッシュダウン・オートマトン」の記事における「計算定義 1」の解説
任意のPDA、 M = ( Q , Σ , Γ , δ , q 0 , F ) {\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)} について、計算経路の順序は (n+1)-タプル ( q 0 , q 1 , . . . . , q n ) {\displaystyle (q_{0},\,q_{1},....,\,q_{n})} で表され（ここで q i ∈ Q , n ≥ {\displaystyle q_{i}\in Q,n\geq } 0 ）、以下の条件が成り立つ。 i = 0 , 1 , 2 , … , n − 1 {\displaystyle i=0,1,2,\dots ,n-1} について、 ( q i + 1 , b i + 1 ) ∈ δ ( q i , w i + 1 , a i + 1 ) {\displaystyle \ \ (q_{i+1},b_{i+1})\in \delta (q_{i},w_{i+1},a_{i+1})} ここで w i + 1 ∈ Σ ϵ , a i + 1 , b i + 1 ∈ Γ ϵ {\displaystyle w_{i+1}\in \Sigma _{\epsilon },\ a_{i+1},\ b_{i+1}\in \Gamma _{\epsilon }} ∃ s 0 , s 1 , s 2 , s 3 , … , s n ∈ Γ ∗ {\displaystyle \exists \,s_{0},\,s_{1},\,s_{2},\,s_{3},\,\dots ,\,s_{n}\,\in \Gamma ^{*}} について s i = a i + 1 t i , s i + 1 = b i + 1 t i , t i ∈ Γ ∗ {\displaystyle s_{i}=a_{i+1}t_{i},\,s_{i+1}=b_{i+1}t_{i},\,t_{i}\in \Gamma ^{*}} 直観的に、PDA での計算の任意の時点で、スタックのトップから記号を読み取ってそれを他の記号に置換するか、置換せずに単にスタックのトップを削除するか、あるいは読み取らずにスタックに新たに記号を追加するか、なにもしないかという選択肢がある。これらは連立方程式 s i = a i + 1 t i a n d s i + 1 = b i + 1 t i {\displaystyle s_{i}=a_{i+1}t_{i}\,and\,s_{i+1}=b_{i+1}t_{i}} で制御される。 s i {\displaystyle \,s_{i}} は、(i+1)番目の状態遷移の直前のスタックの内容であり、 a i + 1 {\displaystyle a_{i+1}} はスタックのトップから除去される記号である。 s i + 1 {\displaystyle s_{i+1}} は (i+1)番目の状態遷移の直後のスタックの内容であり、 b i + 1 {\displaystyle b_{i+1}} は (i+1)番目の状態遷移に伴ってスタックに追加される記号である。 a i + 1 {\displaystyle a_{i+1}} も b i + 1 {\displaystyle b_{i+1}} も ϵ {\displaystyle \epsilon } の可能性もある。 a i + 1 ≠ ϵ {\displaystyle a_{i+1}\neq \epsilon } かつ b i + 1 ≠ ϵ {\displaystyle b_{i+1}\neq \epsilon } なら、PDA はスタックから記号を読み取り、それを別の記号に置換する。 a i + 1 ≠ ϵ {\displaystyle a_{i+1}\neq \epsilon } かつ b i + 1 = ϵ {\displaystyle b_{i+1}=\epsilon } なら、PDA はスタックから記号を読み取り、単にそれを削除する。 a i + 1 = ϵ {\displaystyle a_{i+1}=\epsilon } かつ b i + 1 ≠ ϵ {\displaystyle b_{i+1}\neq \epsilon } なら、PDA は単に記号をスタックに追加する。 a i + 1 = ϵ {\displaystyle a_{i+1}=\epsilon } かつ b i + 1 = ϵ {\displaystyle b_{i+1}=\epsilon } なら、PDA はスタックを更新しない。 n = 0 {\displaystyle n=0} の場合、計算経路はシングルトンとなる ( q 0 ) {\displaystyle (q_{0})} 。
※この「計算定義 1」の解説は、「プッシュダウン・オートマトン」の解説の一部です。
「計算定義 1」を含む「プッシュダウン・オートマトン」の記事については、「プッシュダウン・オートマトン」の概要を参照ください。
- 計算定義 1のページへのリンク
