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