Σ: アルファベット(有限集合)Ω = Σ ∪ { [, ]}Ω^*:Ω上の語全体からなる集合L_p:Ω上の言語 (括弧言語)- 基底 :
Σの元と空語λ - 帰納ステップ :
u,vがL_pの元ならばuvと[u]は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
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 は帰納的に証明された。
// 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