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