第２版形式言語とオートマトン2012 ー第8日目ー東京工科大学コンピュータサイエンス学部亀田弘之今日の内容 1. 練習・練習また練習 2. Pumping定理とその応用 3. Myhill-Nerodeの定理 2 第１部練習 3 練習問題 • まず練習問題をやってみよう。所要時間は１０分。提出は不要ですが、試験対策になるので、各自自力で解いてみてください。 4 問題最簡形DFAを求めよ。 5 解法手順 1. 状態遷移表を作ってみる。 2. 到達不能状態を除去する。 3. 状態遷移表を見て、決定性か非決定性かを確認する。 4. （以下、省略） 6 第２部理論編 8 ポンピングの補題 • 言語LはDFA M により受理されるとする。このときある定整数nが存在して、z∊L, |z| ≧n なる zは、z=uvw, |uv| ≦n, |v|≧1 のように分解され、かつ、uviw ∊ L となる。（この補題は様々な証明等で役立つ。大学院へ進みたい人はしっかり押さえましょう！） 9 ポンピングの補題適用例 • 次の言語が正規言語でないことを示せ。 L  {a b | n  1} n n 10 注意事項 • ポンピングの補題は、言語Lが正規言語であるための必要条件であり、必要十分条件では n m m ない。例えば、言語L’=｛ c a b ｝は、ポンピングの補題を満たすが、正規言語ではない。 n i (c c)c (a b )  L i m m 11 MyHill-Nerodeの定理 • 次の３つの命題は同値である。 1. 言語 L  * は正規言語である。 2. L は、指数が有限かつ右不変な * 上の同値関係 R による同値類の和として表わされる。 3. 任意の z  * に対して、 xz  L  yz  L のとき x  L y と定義すると、 *上の２項関係  L は指数が有限な同値関係である。 12 証明のための準備 • • • • 同値関係 * * 関数  (q, x )   ( (q, x), ) 同値類同値関係の指数 13 関係 • 集合 X と Y の直積 X  Y に対して、その部分集合 R  X  Y を２項関係、あるいは、単に関係という。 • ( x, y)  R のとき、x と yは「 R の関係にある」といい、 xRy と書く。 • R  X  X のとき、RはX上の関係と呼ぶ。 14 関係の例 • （板書します） 15 同値関係 • Ａ上の関係Rが以下の条件を満たすとき、関係Rのことを特に同値関係と呼ぶ。 1. xRx for any x∈Ａ. 2. xRy  yRx for any x, y ∈Ａ. 3. xRy かつyRz ⇒ xRz for any x, y, z ∈Ａ. 16 同値関係の例 • X=Z（整数全体の集合）とする。このとき、x,y∊Zに対して、 x-y が５の倍数  xRy と書くことにすると、RはZ上の１つの同値関係である。 • Zは同値関係Rにより、５つの類に分割される。 • 同値関係の指数とは、同値類の個数のことである。従って、今の場合Rの指数は５である。 17 同値関係Rが右不変 • xRyのとき、xzRyzが成り立つこと。 18 例 • xRy  δ*(q0, x) = δ*(q0, y) のとき、 xRy ⇒ δ*(q0, x) = δ*(q0, y) ⇒ δ*(δ*(q0, x),z) = δ*(δ*(q0, y),z) ⇒ δ*(q0, xz) = δ*(q0, yz) ⇒ xzRyz for z∊Σ* 関係Rは右不変 19 問題 1. 2. 3. 4. 関係の例を２つ以上挙げよ。同値関係の例を２つ以上挙げよ。 modulo n の同値類は全部で何個あるか？内部状態がm個のDFAは、入力文字列を幾つの同値類に分割するか？ 20