オートマトンのテスト前まとめ

注意: 調べたりしながら自分なりにまとめたメモです.正確性は保証しません.


パラメータ

言語のクラス(チョムスキー階層)

言語 文法 オートマトン
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\)

用語集(?)

Tweet