オートマトンのテスト前まとめ
注意: 調べたりしながら自分なりにまとめたメモです．正確性は保証しません．
パラメータ
- 言語 \(G=(N,\Sigma, P, S)\)
- \(N\): 非終端記号の有限集合
- \(\Sigma\): 終端記号の有限集合
- \(P\):生成規則の有限集合
- \(S\): 開始記号 \(S \in N\)
- 有限オートマトン(fa) \(M=(Q,\Sigma,\delta,q_o,F)\)
- \(Q\): 内部状態の有限集合
- \(\Sigma\): 入力記号の有限集合
- \(\delta\): \(Q\times \Sigma \rightarrow Q\): 遷移関数
- \(q_0 \in Q\): 初期状態
- \(F \subseteq Q\): 最終状態（受理状態）の集合
- プッシュダウン・オートマトン(pda) \(M=(Q,\Gamma,\Sigma,\Delta,c_s,F)\)
- \(Q\): 内部状態の有限集合
- \(\Gamma\): スタック記号の有限集合
- \(\Sigma\): 入力記号の有限集合
- \(\Delta\): \(Q\times \Gamma \times (\Sigma\cup\{\varepsilon\})\rightarrow Q \times \Gamma^*\): 遷移規則の集合
- \(c_s \in Q\times\Gamma\): 初期モード
- \(F \subseteq Q\times(\Gamma\cup\{\varepsilon\})\): 最終状態（受理状態）の集合
- Turing機械(TM) \(T=(Q,\Gamma,\Sigma,\delta,q_0,F)\)
- \(Q\): 状態の有限集合
- \(\Gamma\): テープ記号の有限集合 \(B\in\Gamma\)は空白記号
- \(\Sigma\subseteq(\Gamma - \{B\})\): 入力記号の集合
- \(\delta\): \(Q\times \Gamma \rightarrow Q\times(\Gamma - \{B\})\times\{L,R,N\}\): 状態関数，動作関数
- \(q_0 \in Q\): 初期状態
- \(F \subseteq Q\): 最終状態（受理状態）の集合
- 線形有界オートマトン(LBA): TMと同じ
言語のクラス(チョムスキー階層)
| 型 | 言語 | 文法 | オートマトン | 例 |
|---|---|---|---|---|
| 3型 | 正規言語 | 正規文法 | 有限オートマトン | \(a^n b^m\) |
| 2型 | 文脈自由言語 | 文脈自由文法 | プッシュダウン・オートマトン | \(a^n b^n, wcw^R, ww^R\) |
| 1型 | 文脈依存言語 | 文脈依存言語 | 線形有界オートマトン | \(a^n b^n c^n, ww\) |
| 帰納的言語 | ? | ? | ? | \(\{x_i|x_i \notin L(G_i)\}\) |
| 0型(帰納的加算言語) | 句構造言語 | 句構造文法 | チューリング機械 | \(\{x_i|x_i \in L(T_i)\}\) |
| 計算不能言語 | ? | ? | ? | \(\{x_i|x_i \notin L(T_i)\}\) |
\(x_i\): \(\Sigma^*\)
\(G_i\): CS文法
\(T_i\): Turing機械の列挙
言語の特性
| 演算 | 正規言語 | CF言語 | CS言語 | 0型言語 |
|---|---|---|---|---|
| \(L_1 \cup L_2\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) |
| \(L_1\cdot L_2\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) |
| \(L^*\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) |
| \(\Sigma^* - L\) | \(\bigcirc\) | \(\times\) | \(\bigcirc\) | \(\times\) |
| \(L_1 \cap L_2\) | \(\bigcirc\) | \(\times\) | \(\bigcirc\) | \(\bigcirc\) |
| \(L^R\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) |
| \(L_1 \cap R\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) | \(\bigcirc\) |
memo1: \(A\cap B = \overline{\bar A \cup \bar B}\)
memo2: \(\bar A = \Sigma^* - A\)
用語集(?)
ポストの対応問題(PCP)
解の有無を判定できるアルゴリズムは存在しないことを証明するための問題．これが存在すると仮定すると停止性問題が解ける．万能チューリング機械
任意のTMと入力を与えたとき，その動作をシミュレートできるTM．テープはコードとデータに分けて使う．チューリング機械の停止問題
任意のTMと任意の入力を与えたときにそのTMが停止するかという問題．非可解．
クリーネ閉包
\(\Sigma^* = \{\varepsilon\} \cup \Sigma \cup \Sigma^2 \cup \cdots = \cup^\infty_{i=0} \Sigma^i\)
\(\Sigma=\{0,1\}\)のとき，\(\Sigma^* = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \cdots\}\)