[오토마타] 귀납법을 이용한 증명(Proof by mathematical induction)

Proof by mathematical induction

1. For some n₀≥1, P_n0 is true
2. For any k≥_n0, turth of P_k → truth of P_(k+1).
3. If 1& 2 are satisfied, then all P₁, P₂, ... are true.

귀납법에 의한 증명은 아래 3단계로 진행된다.

 

[basis] P1이 사실임을 증명한다. (P를 구하는 식에 직접 1을 넣어서 계산 해 보인다.)

[inductive assumption] P1, P2, ...,Pn는 사실이라고 가정한다.

[inductive step] 1보다 큰 n을 하나 잡고 Pn은 사실인 경우 하나를 보인다. P1이 사실이고, Pn이 true일때, P(n+1)이 true이라면 모든 경우가 true이라는 가정이 성립되는 것이다.

왜냐하면 P1이 true라면 P(n+1) 즉 P2도 true라는 것이고 이런식으로 하나씩 진행시키면 n이 어떤 무한대까지 가더라도 true란 사실은 당연한 것이기 때문이다. 예를 보자.

 

Ex1) Sum of all positive integers not larger than n is n(n+1)/2

[basis] n = 1, 1(1+1)/2 = 1 성립

[assumption] n = k then k(k+1)/2 = n 임을 가정

[induction] n = k+1 일때, k(k+1)/2 + (k+1) = (k(k+1) + 2k + 2)/2 = k(k+3)/2 = k+1(k+2)/2 성립

 

Ex2) Number of leaves of a binary tree with height n≤2²

[basis] n = 1 일때, 바이너리 트리의 leaf는 1개이다. 성립.

[assumption] n = k 일때, leaf 개수는 2^k보다 작다고 가정

[induction] n = k+1 일때, leaf 개수는 k 의 리프 개수보다 2배 이상 많을 수 없다(최대 child가 2이므로). 즉, n = k 일때, leaf 개수가 2^k보다 작다면 n = k+1 일때 leaf 개수는 2^k + a

a ≤ 2^k x 2 즉, 성립

 

 

오토마타에 적용된 Induction 예제를 보자

 

Ex3) Grammar G가 다음과 같이 정의 되었다. G=({A,S}, {a,b}, S, P), P : S → aAb|λ, A → aAb|λ L(G) = {aⁿbⁿ|n≥0} 이 됨을 증명하시오.

 

두가지 경우로 나누어 생각한다.

 

(a) ∀w ∈ L, Sw

[basis] n = 0 일때, w = λ, S ⇒ λ 로 성립함.

n = 1 일때, w = ab, S ⇒ aAb ⇒ ab이 성립함.

[assume] n = k 일때, w = a^kb^k, Sa^kSb^k 임을 가정

[inducton] n = k+1 일때, w = a^k+1b^k+1 에 대해  Sa^kb^ka^kaAbb^ba^k+1b^k+1  이 성립함

 

L에 속하는 모든 w는 S가 여러번의 variation을 거침으로서 만들어 질 수 있단 것을 증명 하였다.

 

(b) ∀w, if S w then w ∈ L

* Let n is variation step

[basis] n = 1 일때, S ⇒ λ = a⁰b⁰ ∈ L 이 성립함

[assume] n = k 일때, S ⇒^k+1 a^k'Ab^k' ⇒ a^k'b^k' ∈ L 임을 가정

[induction] n = k+1 일때, S ⇒^k-1 a^k'Ab^k' ⇒ a^k'aAbb^k' ⇒ a^k'+1Ab^k'+1∈ L 이 성립함.

 

그러므로 모든 원소들이 S가 여러번 variation된 w로 만들어 지고, 이렇게 만들어진 x ∈ L 이므로 처음 증명 하고자 했던 Grammar는 L(G)임이 성립한다.