Aritalab:Lecture/Automata/Regular - Revision history

Adm: /* 有限オートマトンの能力 */

2013-05-07T01:41:26Z

‎有限オートマトンの能力

2013-05-07T01:38:03Z

‎εNFAとNFAの等価性

2013-05-07T01:36:59Z

‎有限オートマトンの能力

2013-05-07T01:36:41Z

‎NFAとDFAの等価性

2013-05-07T01:28:58Z

‎決定性有限オートマトン

2013-05-07T01:28:27Z

‎決定性有限オートマトン

2012-05-07T08:02:08Z

‎NFAとDFAの等価性

2012-05-07T07:53:10Z

‎非決定性有限オートマトン

2012-05-07T07:52:42Z

‎非決定性有限オートマトン

2012-05-07T07:52:27Z

‎非決定性有限オートマトン

@@ Line 144: / Line 144: @@
 言語 x の具体例として 0<sup>n</sup> を考えてみます。0<sup>2n</sup>だけを認識するオートマトンは、言語 {0<sup>n</sup>1<sup>n</sup> | n &ge; 0 } の場合と同じ証明手順により、構築できないことがわかります。
-上記の例はいずれも、n が無限である点に注意してください。例えば、言語 {0<sup>n</sup>1<sup>n</sup> | 10000 &ge; n &ge; 0 } であれば有限オートマトンで認識できます。
+上記の例はいずれも、n が無限である点に注意してください。例えば、言語 {0<sup>n</sup>1<sup>n</sup> | 10000 &ge; n &ge; 0 } であれば有限オートマトンで認識できます。しかし、括弧の対応を認識できない事実は致命的です。全てのプログラミング言語を含む、括弧の対応づけを要する言語を有限オートマトンは認識できないことを意味するからです。
 <div align=right>
 次→　[[Aritalab:Lecture/Automata/ContextFree|文脈自由言語]]

@@ Line 87: / Line 87: @@
 ここまでの話を総合すると、
-: DFAで受理できる言語 = NFAで受理できる言語 = &epsilon;NFAで受理できる言語
+: DFAで受理できる言語のクラス ＝ NFAで受理できる言語のクラス ＝ &epsilon;NFAで受理できる言語のクラス
 となります。

← Older revision		Revision as of 01:36, 7 May 2013
Line 148:		Line 148:
	次→　[[Aritalab:Lecture/Automata/ContextFree\|文脈自由言語]]		次→　[[Aritalab:Lecture/Automata/ContextFree\|文脈自由言語]]
	</div>		</div>
		+
		+	<references/>

@@ Line 73: / Line 73: @@
 : S<sub>2</sub> = { q | q &isin; &delta;(p,a) となる状態 p &isin; S<sub>1</sub>が存在する }
 ここで、S<sub>1</sub>　S<sub>2</sub> をそれぞれ単独の状態とみなせば、入力記号 a によって S<sub>1</sub>　&rarr; S<sub>2</sub> と遷移することにおなじです。つまり、N の状態集合の部分集合のそれぞれを状態とするDFA ''D'' を構成し、初期状態として S<sub>0</sub> = { s<sub>0</sub>} を読み替えれば構成できます。こうすると状態数は指数的に増えてしまいますが、受理できる言語のクラスは NFA も DFA も変わらないということになります。 NFA ''N'' の状態数を n とすると、DFA ''D'' の状態数は 2<sup>n</sup> が上限になります。
-実際に 2<sup>n</sup> レベルの状態を必要とする NFA の族が [http://157.1.40.181/naid/110003191841 2000 年に論文]になっています。
+実際に 2<sup>n</sup> レベルの状態を必要とする NFA の族が [http://ci.nii.ac.jp/naid/110003191841 2000 年に論文]になりました<ref>松浦、岩間、Paterson「2^n-α個の決定性状態を要するn状態NFAの族について」電子情報通信学会技術研究報告. COMP, コンピュテーション 100(402), 17-24, 2000-10-20</ref>。
 ==&epsilon;入力つき非決定性有限オートマトン==

@@ Line 35: / Line 35: @@
 : 任意の s &isin; K, a &isin; &Sigma;, x &isin; &Sigma;<sup>*</sup> に対して &delta;'(s, &epsilon;) = s かつ &delta;'(s, xa) = &delta;(&delta;'(s, x), a)
 この写像を、これからは &delta; と書きます。状態遷移関数を
-: &delta; : K &times; &Sigma; &rarr; K から K &times; &Sigma;<sup>*</sup> &rarr; K
+: &delta; : K &times; &Sigma; &rarr; K 　から　 K &times; &Sigma;<sup>*</sup> &rarr; K
 に拡張したわけです。

@@ Line 58: / Line 58: @@
 です。つまり、各入力記号に対して→が複数あってもよく、また存在しなくてもよいというものです。ここでも &delta; の定義を拡張します。
 : 任意の s &isin; K, a &isin; &Sigma;, x &isin; &Sigma;<sup>*</sup> に対して &delta;'(s, &epsilon;) = s
-: かつ &delta;'(s, xa) = {q | p = &delta;'(s, x), q = &delta;(p,a) となる p &isin; K が存在する }
+: かつ &delta;'(s, xa) = { q | p = &delta;'(s, x), q = &delta;(p,a) となる p &isin; K が存在する }
 最後の「が存在する」という部分が重要です。与えられた記号列 x を読んで &delta;(s<sub>0</sub>, x) に少なくともひとつの受理状態が含まれれば、その列　x は受理されるといいます。いかなる受理状態にも到達できないときに、受理されないといいます。

@@ Line 53: / Line 53: @@
 ==非決定性有限オートマトン==
-Java で正規表現を使うとき、Pattern, Machter というクラスを利用します。[[http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/regex/Pattern.html API仕様]にいきなり「NFA ベースのマッチング」と書いてありますが、その NFA のことです。
+Java で正規表現を使うとき、Pattern, Machter というクラスを利用します。[http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/regex/Pattern.html API仕様]にはいきなり「NFA ベースのマッチング」と書いてありますが、その NFA のことです。
 非決定性オートマトン (NFA: Nondeterministic Finite Automaton) はDFAと同じ M = (K, &Sigma;, &delta;, s<sub>0</sub>, F) で与えられます。異なるのは状態遷移関数だけで、
 : K &times; &Sigma; &rarr; {s<sub>i</sub>,.. s<sub>j</sub> } &nbsp; (s &isin; K)