Aritalab:Lecture/Automata/PushDown - Revision history

Adm at 03:05, 7 May 2012

2012-05-07T03:05:09Z

Adm: /* PDAの具体例と考え方 */

2012-01-06T03:10:29Z

‎PDAの具体例と考え方

Adm: /* PDAの具体例と考え方 */

2012-01-06T03:09:23Z

‎PDAの具体例と考え方

Adm: /* PDAの具体例と考え方 */

2012-01-06T03:08:17Z

‎PDAの具体例と考え方

Adm: /* まとめ */

2012-01-06T03:06:57Z

‎まとめ

Adm at 03:04, 6 January 2012

2012-01-06T03:04:43Z

Adm at 03:03, 6 January 2012

2012-01-06T03:03:18Z

Adm at 02:54, 6 January 2012

2012-01-06T02:54:55Z

Show changes

Adm: /* 文脈自由言語とPDAの等価性 */

2012-01-05T07:21:02Z

‎文脈自由言語とPDAの等価性

Adm: /* プッシュダウンオートマトン */

2012-01-05T06:52:35Z

‎プッシュダウンオートマトン

@@ Line 3: / Line 3: @@
 |}
 ==まとめ==
 ここでは言語 L = { xx<sup>R</sup> | {0,1}{0,1}* } の受理を例として、プッシュダウンオートマトンと文脈自由言語の等価性を示します。プッシュダウンオートマトンは補助記憶としてスタックを一つ備えています。スタックの大きさは有限でないため（無限大になりうる）、言語 { 0<sup>n</sup>1<sup>n</sup> | n &ge; 0 } も認識できます。0を読んでスタックに 0 を積み、その後 1を読んだ数だけスタックから 0 を取り出します。読み終わったときにスタックがちょうど空になった時だけ受理すれば良いのです。

@@ Line 130: / Line 130: @@
 |}
-上の例でわかるように状態遷移関数からPDAの動作を推測するのは大変です。
+上の例でわかるように状態遷移関数からPDAの動作を推測するのは大変です。ただ、スタックを用いて xx<sup>R</sup> が認識できることはわかります。
 ==文脈自由言語とPDAの等価性==

@@ Line 113: / Line 113: @@
+|
 {|
-| Aを積む<br/>状態 s<sub>1</sub>へ
+| Aを積む
 |}
-| ポップ
+| 状態 s<sub>1</sub>へ<br/>ポップ
+|
 {|

@@ Line 113: / Line 113: @@
+|
 {|
-| Aを積む
+| Aを積む<br/>状態 s<sub>1</sub>へ
 |}
-| ポップ<br/>状態 s<sub>1</sub>へ
+| ポップ
+|
 {|

@@ Line 4: / Line 4: @@
 ==まとめ==
-ここではプッシュダウンオートマトンと文脈自由言語の等価性を示します。プッシュダウンオートマトンは補助記憶としてスタックを一つ備えています。スタックの大きさは有限ではなく（無限大になりうる）、言語 { 0<sup>n</sup>1<sup>n</sup> | n &ge; 0 } も簡単に認識できます。0を読んでスタックに 0 を積み、その後 1を読んだ数だけスタックから 0 を取り出します。読み終わったときにスタックがちょうど空になった時だけ受理すれば良いのです。
+ここでは言語 L = { xx<sup>R</sup> | {0,1}{0,1}* } の受理を例として、プッシュダウンオートマトンと文脈自由言語の等価性を示します。プッシュダウンオートマトンは補助記憶としてスタックを一つ備えています。スタックの大きさは有限でないため（無限大になりうる）、言語 { 0<sup>n</sup>1<sup>n</sup> | n &ge; 0 } も認識できます。0を読んでスタックに 0 を積み、その後 1を読んだ数だけスタックから 0 を取り出します。読み終わったときにスタックがちょうど空になった時だけ受理すれば良いのです。
 ==プッシュダウンオートマトン==

← Older revision		Revision as of 03:04, 6 January 2012
Line 312:		Line 312:

	逆に任意の文脈自由言語が与えられたら、それをグライバッハ標準形に直して状態遷移関数とみなすことで１状態PDAに等しいことがわかります。		逆に任意の文脈自由言語が与えられたら、それをグライバッハ標準形に直して状態遷移関数とみなすことで１状態PDAに等しいことがわかります。
		+
		+	<div align=right>
		+	次→　[[Aritalab:Lecture/Automata/TM\|チューリング機械]]
		+	</div>

← Older revision		Revision as of 03:03, 6 January 2012
Line 1:		Line 1:
		+	{\| style="float:right"
		+	\| __TOC__
		+	\|}
		+
	==まとめ==		==まとめ==
	ここではプッシュダウンオートマトンと文脈自由言語の等価性を示します。プッシュダウンオートマトンは補助記憶としてスタックを一つ備えています。スタックの大きさは有限ではなく（無限大になりうる）、言語 { 0<sup>n</sup>1<sup>n</sup> \| n ≥ 0 } も簡単に認識できます。0を読んでスタックに 0 を積み、その後 1を読んだ数だけスタックから 0 を取り出します。読み終わったときにスタックがちょうど空になった時だけ受理すれば良いのです。		ここではプッシュダウンオートマトンと文脈自由言語の等価性を示します。プッシュダウンオートマトンは補助記憶としてスタックを一つ備えています。スタックの大きさは有限ではなく（無限大になりうる）、言語 { 0<sup>n</sup>1<sup>n</sup> \| n ≥ 0 } も簡単に認識できます。0を読んでスタックに 0 を積み、その後 1を読んだ数だけスタックから 0 を取り出します。読み終わったときにスタックがちょうど空になった時だけ受理すれば良いのです。

@@ Line 103: / Line 103: @@
 ==文脈自由言語とPDAの等価性==
-PDAはわざと非決定性に定義してあります。その使い方をまず説明しましょう。
+PDAはわざと非決定性に定義してあります。ここではそのメリットをフルに活かします。
 ; 任意の決定性有限オートマトン (DFA) は、プッシュダウンオートマトンで動作を模倣できる
@@ Line 112: / Line 112: @@
 ===任意のPDAと1状態PDAの等価性===
-スタックを利用できる機能は大変強力で、実は任意の有限状態 PDA を 1 状態のPDAで模倣できます。
+スタックを利用できる機能は大変強力です。実は、任意の有限状態 PDA を 1 状態のPDAで模倣できます。

@@ Line 4: / Line 4: @@
 ==プッシュダウンオートマトン==
-状態 K, 入力記号　&Sigma;, スタック記号 &Gamma; の各有限集合を与えられたとき、プッシュダウンオートマトン (PDA) は M = ( K, &Sigma;, &Gamma;, &delta;, s<sub>0</sub>, z<sub>0</sub> ) で与えられます。s<sub>0</sub> &isin; K, z<sub>0</sub> &isin; &Gamma; はそれぞれ初期状態、スタック上の初期記号です。&delta; は状態遷移関数ですが、有限オートマトンの時と異なり、K &times; &Sigma; &times; &Gamma; から K &times; &Gamma;<sup>*</sup> の'''有限部分集合族の'''中への写像となっています。（有限オートマトンの時は、有限部分集合族ではなく、K &times; &Gamma;<sup>*</sup> 中への写像でした。）つまり、最初から非決定性のオートマトンとして定義します。またスタック初期記号 z<sub>0</sub> を利用するのは、状態遷移関数の定義としてスタックの中身が最初に空であると困るからです。ここで PDA の定義に受理状態 F ⊂ K が入っていない理由は後述します。
+状態 K, 入力記号　&Sigma;, スタック記号 &Gamma; の各有限集合を与えられたとき、プッシュダウンオートマトン (PDA) は M = ( K, &Sigma;, &Gamma;, &delta;, s<sub>0</sub>, z<sub>0</sub> ) で与えられます。s<sub>0</sub> &isin; K, z<sub>0</sub> &isin; &Gamma; はそれぞれ初期状態、スタック上の初期記号です。&delta; は状態遷移関数ですが、有限オートマトンの時と異なり、K &times; &Sigma; &times; &Gamma; から K &times; &Gamma;<sup>*</sup> の'''有限部分集合族の'''中への写像となっています。（有限オートマトンの時は、有限部分集合族ではなく、K &times; &Gamma;<sup>*</sup> 中への写像でした。）つまり、最初から非決定性のオートマトンとして定義します。またスタック初期記号 z<sub>0</sub> を利用するのは、状態遷移関数の定義としてスタックの中身が最初に空であると困るからです。ここで PDA の定義に受理状態 F (⊂ K) が入っていない理由は後述します。
 ===様相===
 動作途中におけるPDAの状況を様相と呼び、状態 s, 読み残している入力記号列 y &isin; &Sigma;<sup>*</sup>, スタックの内容 &sigma; &isin; &Gamma;<sup>*</sup> の組 ( s, y, &sigma; ) で表します。様相が与えられれば、PDAの動作は一意に決まる点に注意してください。
 様相 S<sub>1</sub> から S<sub>2</sub> に状態遷移関数によって移るとき S<sub>1</sub> &rArr; S<sub>2</sub>　と書きます。何ステップかで移動するときは、S<sub>1</sub> &rArr;<sup>*</sup> S<sub>2</sub> と書きます。ある文字列 x を入力としてPDAを動かし、スタックの中身がちょうど空になるとき、 x は PDA によって受理されるといいます。様相で書くと
@@ Line 16: / Line 21: @@
 です。PDAでは受理状態というものを定義せず、入力文字列を読み終わったときにスタックが空であれば受理とみなします。こうすると、後で文脈自由言語との等価性を示すのが楽になるからです。
 ==文脈自由言語とPDAの等価性==