Aritalab:Lecture/Automata/ContextFree - Revision history

Adm at 03:04, 7 May 2012

2012-05-07T03:04:45Z

Adm: /* uvwxy定理 */

2012-01-06T03:02:50Z

‎uvwxy定理

Adm: /* uvwxy定理 */

2012-01-06T03:02:20Z

‎uvwxy定理

Adm: moved Aritalab:Lecture/Basic/Automata/ContextFree to Aritalab:Lecture/Automata/ContextFree

2011-06-01T15:38:26Z

moved Aritalab:Lecture/Basic/Automata/ContextFree to Aritalab:Lecture/Automata/ContextFree

Adm at 15:38, 1 June 2011

2011-06-01T15:38:11Z

Adm at 07:57, 25 November 2010

2010-11-25T07:57:31Z

Adm at 03:10, 25 November 2010

2010-11-25T03:10:02Z

Adm: /* uvwxy定理 */

2010-10-30T02:30:56Z

‎uvwxy定理

Adm: /* uvwxy定理 */

2010-10-30T01:59:35Z

‎uvwxy定理

Adm: /* uvwxy定理 */

2010-10-29T09:01:27Z

‎uvwxy定理

@@ Line 2: / Line 2: @@
 |__TOC__
 |}
-==概略==
+[[Aritalab:Lecture/Automata|形式言語理論のトップページヘ]]
 文脈自由文法では正則表現よりも複雑な言語に属する列を生成できます。
 文脈自由文法は書換え規則の集合として表現され、

@@ Line 117: / Line 117: @@
 <div align=right>
-次→　[[Aritalab:Lecture/Automata/PushDown|プッシュダウンオートマトン]
+次→　[[Aritalab:Lecture/Automata/PushDown|プッシュダウンオートマトン]]
 </div>

@@ Line 112: / Line 112: @@
 ; L = { zz | z &isin; {0,1}<sup>*</sup> } はCFGで書けない
 zz は u=w=y=&epsilon;とおけば uvwxy で表現できるように思えますが、上の定理は十分条件ではありません。例えば z = 0<sup>n</sup>1<sup>n</sup> とおくと、L は　0<sup>n</sup>1<sup>n</sup>0<sup>n</sup>1<sup>n</sup> という列を含みますが、これはCFGで書けません。
 <div align=right>
-次→　[[Aritalab:Lecture/Automata/TM|チューリング機械]]
+次→　[[Aritalab:Lecture/Automata/PushDown|プッシュダウンオートマトン]
 </div>

@@ Line 101: / Line 101: @@
 生成規則には右辺が変数1個だけのものは存在しませんから、v, x の部分は少なくとも片方が &epsilon; ではありません。
 更に、最後に現われた x の部分以降の導出を、それ以前に現われた x の導出と置き換えることにより、uv<sup>i</sup>wx<sup>i</sup>y の列を導出できます (図2)。
-この定理は[[Aritalab:Lecture/Basic/Automata/PumpingLemma|ポンピング補題]]とも呼ばれ、正則言語にも対応する補題があります。
+この定理は[[Aritalab:Lecture/Automata/PumpingLemma|ポンピング補題]]とも呼ばれ、正則言語にも対応する補題があります。
 ; L = { 0<sup>n</sup>1<sup>n</sup>0<sup>n</sup> | n &ge; 1 } はCFGで書けない
@@ Line 114: / Line 114: @@
 <div align=right>
-次→　[[Aritalab:Lecture/Basic/TM|チューリング機械]]
+次→　[[Aritalab:Lecture/Automata/TM|チューリング機械]]
 </div>

@@ Line 3: / Line 3: @@
 |}
 ==概略==
-文脈自由文法では正規表現よりも複雑な言語に属する列を生成できます。
+文脈自由文法では正則表現よりも複雑な言語に属する列を生成できます。
 文脈自由文法は書換え規則の集合として表現され、
 殆んどのプログラミング言語は文脈自由言語で記述されます。
@@ Line 16: / Line 16: @@
       | NUMBER
 </pre>
-式の中にはカッコ（）の対応が出てくるので、四則演算の式は正規表現で表現できないことに注意しましょう。
+式の中にはカッコ（）の対応が出てくるので、四則演算の式は正則表現で表現できないことに注意しましょう。
 文脈自由文法をオートマトンでシミュレートするにはより複雑な構造が必要です。
-正規表現が有限オートマトンと等価であったように、文脈自由文法はプッシュダウンオートマトン（スタックを備えたオートマトン）と等価なことがわかっています。
+正則表現が有限オートマトンと等価であったように、文脈自由文法はプッシュダウンオートマトン（スタックを備えたオートマトン）と等価なことがわかっています。
 ==文脈自由文法==
@@ Line 67: / Line 67: @@
 ===DFA &sub; CFG ===
-任意の正規言語 L に対して、それを生成するCFGを構成できます。
+任意の正則言語 L に対して、それを生成するCFGを構成できます。
 L はDFAと等価であるため、認識するオートマトンが存在します。
 その各遷移規則 S<sub>i</sub>--(a)-->S<sub>j</sub>に対して、CFGの生成規則 S<sub>i</sub> = aS<sub>j</sub> を作成すればCFGになります。S<sub>j</sub>が受理状態の場合は S<sub>i</sub> = a とします。
@@ Line 101: / Line 101: @@
 生成規則には右辺が変数1個だけのものは存在しませんから、v, x の部分は少なくとも片方が &epsilon; ではありません。
 更に、最後に現われた x の部分以降の導出を、それ以前に現われた x の導出と置き換えることにより、uv<sup>i</sup>wx<sup>i</sup>y の列を導出できます (図2)。
-この定理は[[Aritalab:Lecture/Basic/Automata/PumpingLemma|ポンピング補題]]とも呼ばれ、正規言語にも対応する補題があります。
+この定理は[[Aritalab:Lecture/Basic/Automata/PumpingLemma|ポンピング補題]]とも呼ばれ、正則言語にも対応する補題があります。
 ; L = { 0<sup>n</sup>1<sup>n</sup>0<sup>n</sup> | n &ge; 1 } はCFGで書けない

← Older revision		Revision as of 02:30, 30 October 2010
Line 108:		Line 108:

	; L = { zz \| z ∈ {0,1}<sup>*</sup> } はCFGで書けない		; L = { zz \| z ∈ {0,1}<sup>*</sup> } はCFGで書けない
−	zz は u=w=y=εとおけば uvwxy ~~で表現できますが、上の定理は十分条件ではありません。例えば~~ z = 0<sup>n</sup>1<sup>n</sup> とおくと、L は　0<sup>n</sup>1<sup>n</sup>0<sup>n</sup>1<sup>n</sup> という列を含みますが、これはCFGで書けません。	+	zz は u=w=y=εとおけば uvwxy で表現できるように思えますが、上の定理は十分条件ではありません。例えば z = 0<sup>n</sup>1<sup>n</sup> とおくと、L は　0<sup>n</sup>1<sup>n</sup>0<sup>n</sup>1<sup>n</sup> という列を含みますが、これはCFGで書けません。

@@ Line 85: / Line 85: @@
 ===uvwxy定理===
-L を有限でないCFGとします。すると L によって決まる定数 K が存在し、L に属する任意の列 z について以下の3条件が成り立ちます。
+L を有限でない CFG とします。すると L によって決まる定数 K が存在し、L に属し、長さが K 以上の任意の列 z について以下の3条件が成り立ちます。
 ただしこれは必要条件であり、十分条件ではありません。
 # z= uvwxy
@@ Line 98: / Line 98: @@
 生成規則には右辺が変数1個だけのものは存在しませんから、v, x の部分は少なくとも片方が &epsilon; ではありません。
 更に、最後に現われた x の部分以降の導出を、それ以前に現われた x の導出と置き換えることにより、uv<sup>i</sup>wx<sup>i</sup>y の列を導出できます (図2)。
+この定理は[[Aritalab:Lecture/Basic/Automata/PumpingLemma|ポンピング補題]]とも呼ばれ、正規言語にも対応する補題があります。
 ; L = { 0<sup>n</sup>1<sup>n</sup>0<sup>n</sup> | n &ge; 1 } はCFGで書けない

@@ Line 105: / Line 105: @@
 <sup>n</sup>1<sup>n</sup>0<sup>n</sup> = uvwxy という分解を考えます。
 このとき uv<sup>i</sup>wx<sup>i</sup>y も L に含まれるはずですが、
-v, x の2箇所の繰り返しでは、a,b,c の3文字の繰り返しを表現できないので矛盾します。
+v, x の2箇所の繰り返しでは、a,b,c の3つの繰り返しを表現できないので矛盾します。
 ; L = { zz | z &isin; {0,1}<sup>*</sup> } はCFGで書けない
 zz は u=w=y=&epsilon;とおけば uvwxy で表現できますが、上の定理は十分条件ではありません。例えば z = 0<sup>n</sup>1<sup>n</sup> とおくと、L は　0<sup>n</sup>1<sup>n</sup>0<sup>n</sup>1<sup>n</sup> という列を含みますが、これはCFGで書けません。