オートマトン・形式言語及び演習
— 4.正規言語の性質— 酒井 正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ 4- 1 / 27正規言語の性質
反復補題 正規言語が満たす性質。ある与えられた言語 が正規言語でないことを証明するために、その言語が正 規言語であると仮定して反復補題を使い、矛盾を導く。 閉包性 正規言語を演算により組み合わせて得られる言 語が正規言語となる演算について調べる。複雑なオー トマトンを構成するツールとして利用可能。 状態数の減少技術 実現するチップ面積の減少。 4- 2 / 27反復補題の直観的説明
言語L01={0n1n| n ≥ 1}が正規言語と仮定する。 L01を認識するDFAが存在する。その状態数をkとしよう。 k + 1種類の入力ε, 0, 00, . . . , 0kを考えると、状態数がkな ので、同じ状態にたどり着く入力が少なくとも２種類存在 する。その状態をq,二つの入力を0i、0j (i 6= j)とする。 0i1iは受理されるので、qから受理状態へ1iでたどり着け る。したがって、0j1iも受理してしまい矛盾する。 4- 3 / 27反復補題
定理4.1: (正規言語に対する反復補題) Lを正規言語とするときn > 0が存在して、|w| ≥ nなる任 意のw ∈ Lについても以下を満たす分解w = xyzがある。 1. y 6= ε 2. |xy| ≤ n 3. ∀k ≥ 0, xykz ∈ L 4- 4 / 27反復補題
証明：Lを認識するDFAが存在するので、その状態数でn を定める。 w = a1a2. . .am∈ L, m ≥ n、 pi= δ(p0,a1a2· · · ai) (i = 0, . . . m) とすると、pi=pj, (i < j)を満たすi, jが存在する。(最小の i, jを選ぶ) 図のようにx, y, zを定めると、y 6= εかつ|xy| ≤ nかつ ∀k ≥ 0, xykz ∈ L。 4- 5 / 27反復補題
例：反復補題を利用してLeq(0と1の出現数が等しい文字列 からなる言語)が正規言語でないことを示す。 - Leqが正規言語と仮定。 - 反復補題で定まるnからw = 0n1n∈ Leqを決める。 - y 6= ε, |xy| ≤ n, ∀k ≥ 0, xykz ∈ L eqを満たす分割 w = xyzが存在。(なぜなら|w| ≥ n) - y = 0m(0 <m)より、xzは0と1の個数が異なる文 字列。 - xz ∈ Leqより矛盾。 4- 6 / 27反復補題
例：反復補題を利用してLrev ={uuR| u ∈ {0, 1}∗}が正規言 語でないことを示す。 - Lrevが正規言語と仮定。 - 反復補題で定まるnからw = 0n110n∈ Lrevを決める。 - y 6= ε, |xy| ≤ n, ∀k ≥ 0, xykz ∈ Lrevを満たす分割 w = xyzが存在。(なぜなら|w| ≥ n) - y = 0m(0 <m)より、xz = 0`110n(` <n) - xz ∈ Lrevより矛盾。 4- 7 / 27反復補題
例：反復補題を利用してLpr(素数個の1の文字列からなる言 語)が正規言語でないことを示す。 - Lprが正規言語と仮定。反復補題でnが定まる。 - pをp ≥ n + 2なる素数とする。w = 1pとする。 - y 6= ε, |xy| ≤ n, ∀k ≥ 0, xykz ∈ L prを満たす分割 w = xyzが存在。(なぜなら|w| ≥ n) - |y| = m(m ≥ 1)、w0=xyp−mzとおく。 - w0∈ L pr、また、|w0| = |xyp−mz| = |xyz| + |yp−m−1| = p + m(p − m − 1) = (1 + m)(p − m)。 - p ≥ n + 2とm ≤ |xy| ≤ nより、 p − m ≥ (n + 2) − n ≥ 2。よって、|w0|は素数でないの で、矛盾。 4- 8 / 27正規言語の閉包性
L,Mを正規言語とするとき、以下の言語は正規言語 - 和集合：L ∪ M、積集合：L ∩ M - 補集合：L、差集合：L − M - 反転：LR={wR| w ∈ L} - スター閉包：L∗、連接：L.M - 準同型の像： h(L) = {h(w) | w ∈ L, hは準同型写像} - 準同型の逆像： h−1(L) = {w | h(w) ∈ L, hは準同型写像} 4- 9 / 27正規言語の閉包性
定理4.4：MとM0が正規言語ならば、M ∪ M0も正規言語 証明：M,M0をそれぞれ表す正規表現R,R0が存在する。こ のとき、M ∪ M0=L(R+R0)。 定理4.5：MがΣ上の正規言語ならば、M = Σ∗− Mも正規 言語 証明：Mを認識するDFA A = (Q, Σ, δ, q0,F)が存在する。 このとき、A0= (Q, Σ, δ, q0,Q − F)はMを認識する。正規言語の閉包性
例：(0 + 1)∗01を認識するDFA 例：(0 + 1)∗01の補集合を認識するDFA正規言語の閉包性
定理4.8：LとMが正規言語ならば、L ∩ Mも正規言語 証明1：ドモルガンの法則より、L ∩ M = L ∪ M。正規言語 は和集合と補集合で閉じていることから、L ∩ Mも正規言語 直積を用いて直接L ∩ Mを認識するオートマトンを作 成することも出来る。直接の方が作成の手間がかから ない。正規言語の閉包性
定理4.8：LとMが正規言語ならば、L ∩ Mも正規言語 証明2：L,Mを認識するオートマトンを AL= (QL, Σ, δL,qL,FL) AM= (QM, Σ, δM,qM,FM) とする。これらは(簡単のために)DFAとする。 - ALとAMを同時に模倣するオートマトンAを構成する。 4- 13 / 27正規言語の閉包性
証明2 (続き) - aを読み込んだとき、 ALで状態pからsへ AMで状態qからtへ 遷移する場合、 Aで状態(p, q)から(s, t)へ 遷移するように構成する。 4- 14 / 27正規言語の閉包性
証明2(続き) - 形式的には、 A = (QL× QM, Σ, δ, (qL,qM),FL× FM) ここで、δ((p, q), a) = (δL(p, a), δM(q, a)) - |w|に関する帰納法により次が証明できる δ((qL,qM),w) = (δL(qL,w), δM(qM,w))- これより、L(A) = L(AL)∩ L(AM)が証明される
4- 15 / 27
正規言語の閉包性
例：(c)は(a)×(b) 4- 16 / 27正規言語の閉包性
定理4.10：M,M0が正規言語ならば、M − M0も正規言語 証明：M − M0=M ∩ M0なので、定理4.5、定理4.8より明 らか。 定理4.11：Mが正規言語ならば、MRも正規言語 証明1：Mを認識するオートマトンAから、MRを認識する オートマトンA0を構成する。 - Aの受理状態を一つに変更する。(新しい受理状態qfを 導入し、旧受理状態からqfへε遷移を作る) - 矢印をすべて逆向きにして、受理状態と初期状態を入 れ換えてA0を構成する 4- 17 / 27正規言語の閉包性
定理4.11：Mが正規言語ならば、MRも正規言語 証明2：正規表現Eを反転した言語を表す正規表現ERを帰 納的に与える 基底：εR=ε、∅R=∅、aR=a 帰納： - (F+G)R=FR+GR - (F.G)R=GR.FR - (F∗)R=(FR)∗ このとき、L(ER) = (L(E))RがEの構成に関する帰納法 で証明できる 4- 18 / 27準同型写像
以下の性質を満たす関数h : Σ∗→ Σ0∗を、Σ上の準同型写
像(homomorphism)という。 h(a1a2· · · an) =h(a1)h(a2)· · · h(an)
準同型写像hによる言語Lの像： h(L) = {h(w) | w ∈ L} 例：h(0) = ab, h(1) = εで定まる準同型写像 h : {0, 1}∗→ {a, b}∗を考えるとき、 - h(0011) = ababεε = abab - h(L(10∗1)) =h({11, 101, . . .}) = {ε, ab, . . .} =L((ab)∗) 4- 19 / 27
準同型写像
hから定まる正規表現の変換ˆhの定義： 基底：ˆh(ε) =ε、ˆh(∅) =∅、h(ˆa) =h(a) 帰納： - ˆh(F+G) = ˆh(F)+h(G)ˆ - ˆh(F.G) = ˆh(F).ˆh(G) - ˆh(F∗) = ˆh(F)∗ 例：ˆh(10∗1) =ε(ab)∗ε=(ab)∗ 4- 20 / 27準同型写像
定理4.14：Mが正規言語ならば、その準同型写像による像 h(M)も正規言語 証明：Mを表す正規表現をEとし、L(ˆh(E)) = h(L(E))をE の構成に関する帰納法で示す。 - 基底：E =εまたはE =∅のとき、ˆh(E) = Eより L(ˆh(E)) = L(E) = h(L(E))。- E =a、h(a) = b1· · · bnのとき、 L(ˆh(a)) =L(b1· · · bn) ={b1· · · bn} = h({a}) =h(L(a)) 4- 21 / 27
