Skip to content

Instantly share code, notes, and snippets.

@ytRino
Created November 12, 2012 17:29
Show Gist options
  • Save ytRino/4060689 to your computer and use it in GitHub Desktop.
Save ytRino/4060689 to your computer and use it in GitHub Desktop.
形式言語理論 3 認識問題 命題3.1

形式言語理論 3 認識問題

定義とか

  • Σ: アルファベット(有限集合)
  • Ω = Σ ∪ { [, ]}
  • Ω^* : Ω上の語全体からなる集合
  • L_p : Ω上の言語 (括弧言語)
    • 基底 : Σの元と空語λ
    • 帰納ステップ : u,vL_pの元ならば uv[u]L_pの元

括弧言語L_p の認識問題

  • ρ:Ω -> Z, Zは整数全体からなる集合
    ρ([) = 1, ρ(]) = -1, ρ(a) = 0 (a ∈ Σ)
  • ρ:Ω^* -> Z
    ρ(a_1 a_2 a_3 … a_n) = ρ(a_1)+ρ(a_2)+ρ(a_3)+...+ρ(a_n), a_i ∈ Σ
    特にn = 0 のとき ρ(λ) = 0

命題 3.1

Q^*の元xがL_pの元である必要十分条件は
(i) ρ(x) = 0
(ii) xの任意の前部分語yに対し、ρ(y) >= 0

(=>)

証明: xがL_pの元 => (i)(ii)を満たす

x の構成に関する帰納法
(1) x := Σの元 || λ
    定義よりρ(x) = 0, ρ(y) = 0 よって成り立つ
    
(2) x = uv, u,v ∈ L_p              // => u,vについて成り立つと仮定した時xで成り立つことを示す
    仮定u,vについて(i)(ii)が成り立つ
    ρ(x) = ρ(u) + ρ(v) = 0
    ∴ xについて(i) が成り立つ
    (a) y := uの前部分語
    	ρ(y) >= 0    ∵仮定より  // ρ(u) >= 0はプリントのミス
    (b) y := uz , z := vの前部分語
    	ρ(y) = ρ(u) + ρ(z) >= 0      ∵ 仮定よりρ(z) >= 0
    ∴(a)(b)より(ii)が成り立つので(2)のときも条件を満たす
    
(3) x = [u], u ∈ L_p
	ρ(u) = 0より
	ρ(x) = ρ([) + ρ(u) + ρ(]) = 1 + 0 + -1 = 0
	∴(i)を満たす
	
	y := 任意の前部分語
	ρ(y) > 0
	∴(ii)を満たすので(3)のときも条件を満たす
	
// (1)(2)(3)はL_pの定義なのでそうでないxはそもそもL_pでない
以上より帰納的に、xがL_pの元ならば(i)(ii)を満たすことを示した

(<=)

証明: (i)(ii)を満たす => xはL_pの元

x の長さに関する帰納法
(1) |x| <= 1のとき
    ρ(x) = 0             // (1)
    よりxはΣの元 || λ      // [,]だと0にならない
    ∴ x ∈ L_p
    
(2) x = uv, ρ(u) = 0, u ≠ λ, v ≠ λ
    ρ(x) = ρ(u) + ρ(v) = 0 , ρ(u) = 0 よりρ(v) = 0
 	xが(ii)を満たすからuの任意の前部分語zについてρ(z) >= 0
 	ρ(u) = 0から vの任意の前部分語wについてもρ(w) >= 0
    したがってu,vは共に(i)(ii)を満たすので
    仮定より u ∈ L_p, v ∈ L_p となり             ∵ 仮定: uが(i)(ii)を満たす=>uはL_pの元
    ∴ x ∈ L_p
    
(3) x = yz, y ≠ λ, z ≠ λとなる任意の元yに対し、ρ(y) > 0 だったとする
    xの最初の文字は [ でなければならない        ∵ ρ(y) >= 0 ではなく > 0だから
    よってρ(x) = 0 より最後の文字は ]
    よってx = [u]の形になる
    x=[u]に対して(i)(ii)が成立するからuに対しても成立し、
    仮定よりu ∈ L_p となり
    ∴ x ∈ L_p
    
// (1)(2)(3)に当てはまらないxは、ρ(y)<0となる前部分語yが存在するのでそもそも(i)(ii)を満たさない
以上より帰納的に、xが(i)(ii)を満たすならばxはL_pの元であることを示した

以上より命題3.1 は帰納的に証明された。

括弧言語L_pの認識アルゴリズム

// j = ρ(a_1) + ρ(a_2) + … + ρ(a_n)

a[n];  // 語x
for (i = 1; i <= n; i++) {
    j += ρ(a[i])
    if(j < 0) {
        return false;
    }
}
if(j == 0) {
    return true;
}else {
    return false;
}

要約: 括弧が対応するような文字列ならOK

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment