오토마타 automata - 파서parser

차례

• 언어이론의 기초

• Regular 언어(language)

– 한글 모아쓰기 기계(automata)

• Rewriting System 혹은 파서

– Context-free 언어의 해석(parsing)

• 왼 파서(left parser) - 왼쪽 부터 유도하기(leftmost  derivation)

– 위 아래(top-down) 파서

• 오른 파서(right parser) - 오른쪽부터 유도하기를 거꾸로(rightmost derivation in reversed order)

– 아래 위(bottom-up) 파서

– Deterministic parsing of CFG

• 왼 파서 Strong LL(k) 파서 ⊆ LL(k) 파서.

• 오른 파서 LR(k) 파서 ⊇ LALR(k) 파서 ⊇ SLR(k) 파서.

• 현대수학에서 계산(computable)에 관한 Turing-Church의 주장(Thesis)

– TM Turing 1930.

– μ-recursive 부분함수 Church 1934.

• 현대수학의 비극

– Cantor’s diagonalization argument 1874; 1891.

• uncountable, 실수(實數; real number)

– Russell's 모순(Paradox) 1901; 1911.

– Gödel의 incompleteness theorem 1931.

• Hilbert의 실패한 꿈 1929.

– Halting 문제(problem)과 같은 문제들

• 끝내기 이야기

언어(Languages) – 소통수단

• 인문사회과학

– 철학, 역사, 사회학, 경제, 법률

– 모국어(자연언어)

• 애매(Ambiguous)하다

• 복잡하다

– 영어강의

• ???

• 예술

– 음악, 미술, 스포츠

– 연주, 형태, 행동

• 자연과학, 공학, 전산학

– 수학

• 엄밀 (Rigorous, Formal) 하다

• 간단하다

– 전산학

• 프로그래밍 언어

구문론(構文論; Syntax)

•  

전문용어 4개+

•  

문법(Grammar)

•  

 

•  

문법의 계층(hierarchical)구조

•  

기계(Automata)의 계층구조

• Type 3: 유한상태기계(Finite state automata; FA)

– 상태(stateS), 입력 문자(S), state 변화(transitionS)

– 초기(initial) 상태, 끝나는(finalS) 상태

– 결정적(deterministic), 비결정적(non-deterministic)

– 정규(regular) 문법, 언어

• Type 2: Stack을 가진 기계(Pushdown automata; PDA)

– FA + stack

– 문맥자유(context-free) 문법, 언어

• Type 1, 0: Turing machine(메모리를 가진 기계)

– FA + memory(tape)

– 컴퓨터, 프로그램

• Type 1: TM

– 항상 끝난다(terminate).

– 알고리즘

• Type 0: TM

– 끝나지 않을 수도 있다(infinite loop).

– 프로그램

언어와 문법의 예(1)

•  

언어와 문법의 예(2)

•  

고쳐쓰기(Rewriting system)

•  

정규문법, 문장확인 유한상태기계,

그리고 고쳐쓰기

•  

문맥자유문법 유도

파스(parse) 나무(tree)

•  

 

•  

 

•  

 

•  

왼 파서 - 2

•  

왼 파서의 예상을 예상한다.

결정적(deterministic) SLL(k) 파서

•  

 

•  

 

•  

오른 파서와 LR(1) itemS

•  

오른 파서의 비결정성 줄이기

오른 파서 → LR(k) 파서

•  

LR(k) 파서 만들기

•  

왼 파서의 비결정성 더 줄이기

SLL(k) 파서 → LL(k) 파서

•  

LL(k) 파서 만들기

•  

왼 파서의 종류

•  

오른 파서의 종류

•  

LL, RR/LR, RL 파서

결정적 왼/오른 파서

• 왼 파서의 결정적 파서

– Stack이 유도할 문자열을 미리 계산하여 예상하고 후에 확인한다. 

– SLL(k)문법 ⊆ LL(k)문법이지만

– SLL(1)문법 = LL(1)문법

– 좌 반복(left recursive) 문법은 LL(k)가 아니다.

• A → Aα | β이면

• Firstk(Aα) ⊇ Firstk(A) ⊇ Firstk(β).

• 오른 파서의 결정적 파서

– Stack에 미리 기억하고 후에 확인한다.

• 왼 파서는 (성실한) 미래학자이고,

– Stack에 있는 미래(우문맥(right context))를 미리 예측하고 확인한다.

• 오른 파서는 (성실한) 역사학자이다.

– Stack에 과거(좌문맥(left context))를 기억하여 정리하고 확인한다.

• … ⊆ LL(k)문법 ⊆ SLR(k)문법 ⊆ …

Turing 기계(machine)는 컴퓨터다.

• Turing 기계(machine; TM) Turing 1930.

• M = (Q, Σ, Γ, →TM, qs, qf)

– Q: StateS

– Σ: 입력문자 Γ: Tape 문자(Σ ⊆ Γ, B ∈ Γ, B ¬∈ Σ)

– qs ∈ Q: 시작 상태 qf ∈ Q: 마지막 상태.

– TM의 상태: QⅹΓ*ⅹΓ*: StateⅹTape 왼쪽내용ⅹTape 오른쪽내용.

– (q, αZ, Xβ) →TM(p/Y/L) (p, αZY, β)

– (q, αZ, Xβ) →TM(p/Y/R) (p, α, ZYβ)

• L(TM) = {w ∈ Σ*| (q0, ε, w) ⇒TM* (qf, α, β)}.

• TM은 메모리에 읽고 쓰고, head를 움직일 수 있다.

• TM은 컴퓨터다.

– 1 cell을 32bit로 확장(word)한다.

– 단일 head를 다중 head로 바꿀 수 있다.

• Register, memory

– 산수와 논리(ALU)를 흉내 낼 수 있다.

– Program 메모리와 data 메모리를 구분한다.

• Von Neumann 구조

• Stored(Programmable) control logic

– Hardware vs. Software

• TM은 프로그램이다.

TM은 프로그램이다

• 프로그램의 꽃

– 반복(재귀)구조(loop)

• 변하지 않는 (loop invariance) 성질

• 변하는 (loop termination) 성질

• 반복구조(loop)의 문제

– 끝나지 않을 수(infinite loop)도 있다

• 항상 끝나는 프로그램(알고리즘)

– Type 1

– Recursive

– 전체(total) 함수

• 끝나지 않은 수 도 있는 프로그램

– Type 0

– Recursively enumerable

– 부분(partial) 함수

• Recursively enumerable 밖에는 무엇이 있나?

– 프로그램 할 수 없는 문제들

함수와 컴퓨터(프로그램, TM)

•  

TM, 최소화 재귀함수,

Turing-Church의 주장

• Ackermann함수는 기초재귀로는 안 된다.

A(0, y) = y+1

A(x+1, 0) = A(x, 1)

A(x+1, y+1) = A(x, A(x+1), y))

• μ-(최소화)재귀함수 – Church 1934; lecture at Princeton

f(x) = μ n [g(x, n) = 0]

   Min n: [g(x, n) = 0 ∧ (1 ≤ ∀k ≤ n: ∃g(x, k)]

• Turing의 주장

– TM(프로그램)은 계산가능(computable, programmable)이다.

• TM  ⇒ 계산가능.

– 계산가능은 TM(프로그램)이다(?)라고 주장(Thesis)

• TM  ⇔ 계산가능.

• Church의 주장

– μ-재귀함수는 TM으로 프로그램할 수 있다.

– TM도 μ-재귀함수로 표현할 수 있다.(증명)

• TM ⇔ μ-재귀함수.

– 계산가능은 μ-재귀함수이기도 하다.

• Turing-Church의 주장

– 계산가능은 프로그램(TM)이나 μ-재귀함수이다.

• 프로그램  ⇔ μ-재귀함수 ⇔ 계산가능(?)

– 계산가능은 λ-calculus(Church 1934, Kleene 1935, Rosser 1935)다.

– 계산가능은 combinatory logic(Schönfinkel 1924, Curry 1929)이다.

– 계산가능은 type 0 grammar(Chomsky 1959)이다.

Cantor의 대각선화 주장(1874; 1891)

비극의 시작

• 무한이진수 ↔ 자연수(셀 수 있게 무한)이라고 하자.

• a1 = 00000…

• a2 = 11111…

• a3 = 01101…

• …

• a = 011 … 대각선화(diagonalization)

• ￢a = 100 … 대각선화의 부정

• a, ￢a ∈ 무한이진문자열,

그러나, a ↔ 자연수, ￢a ￢↔ 자연수.

• 무한이진수 ￢↔ 자연수.

– |자연수의 부분집합| > |자연수|

• 자연수 셀 수 있게(countable) 무한(많다)

• 자연수의 부분집합 셀 수 없이(uncountable) 무한(많다)

• 증명의 핵심

– 대각선화(diagonalization) 후에 부정한다.

• Russell에 영향을 준 것으로 예상.

– Self-recursion에 대한 부정.

– 내 개인 생각

Russell의 모순(paradox, 1901; 1911)

• Cantor의 naive set theory에 대한 부정

• Let R = {x| x ￢∈ R}

• 매우 아름다운 집합에 대한 정의

– 집합도 집합의 원소가 될 수 있다.

• {{}, {{}}, {{{}}}, …}

– 집합이 그 집합 자신을 원소로 갖는 것은 이상하다.

• 사각형의 집합이 사각형의 집합을 원소로 가지지 않는다.

– 그러나,

• in x = R then (R ∈ R) ⇔ (R ￢∈ R).

• 자기자신으로 재귀(self-recursion)에 대한 부정.

• 자신을 부정하는 사람은 존재하지 않는다.

Hilbert의 실패한 꿈(1929)

Gödel의 불완전성 정리(1931)

• Hilbert의 꿈(program), 1929.

– 공리(axiom)로 시작한 완전하고(complete) 일관된(consistent) 수학(정리, theorem; 식, formula)의 모든 정리(theorem)는 일관된 증명(proof; 프로그램)이 있다.

• Gödel의 불완전성 정리(Incompleteness Theorem), 1931.

– 증명(proof)도 정리(theorem)다.

• 완전하고 일관된 공리를 가진 수학은 없다.

• 자신의 일관됨을 주장하는 정리는 일관되지 않다.

• Gödel의 불완전성 정리의 증명

– G(T): 정리 → Gödel수: 정리 T의 Gödel수

– prov: Gödel수 → 수; prov(G(T)) = G(p) if ∃p: 정리 T의 증명; = Gödel수가 아닌 수, otherwise.

– p ⇔ F(G(p))

– Consider Beweisbar(y: Gödel수) = ∃x: ((y = G(T): T: x의 정리) ∧ (x = G(p): (p: y의 증명))

– Beweisbar(Gödel의 모국어인 독일어로 provable)는 너무 길다.

• Beweisbar(y) = G(p): (p: y의 증명)

• Gödel수(증명 ↔ 정리 ↔ 자연수)도 필요 없다.

• Bew(T: 정리) = if prov(T) → true | ￢prov(T) → false fi.

• Bew(T) = F(T).

• 대각선화(diagonalization)하고 부정한다.

• ￢Bew(T: 정리) = if prov(T) → false | ￢prov(T) → true fi.

• ￢Bew(T) = ￢F(T).

• Self recursion

– ￢Bew(Bew) = ￢prov(prov) ⇔ prov(prov) = Bew(Bew).

Halting problem과 같은 문제들

• Let H(p, d) = if p(d) stops → ￢stop

 | p(d) ￢stop → stops

fi.

• in p = d = H

• then H(H, H) stops ⇔ H(H) ￢stop ⇔ H(H, H) ￢stop.

• 거짓말쟁이 개똥이가, “이 글은 내가  썼다”

그 글을 개똥이가 썼나, 안 썼다?

• 이발 못하는 사람만 이발해주는 이발사.

자신이 자신을 이발 할 까, 안 할 까?

• 이종형용사(Heterological)는 이종형용사인가 아닌가?

– 형용사가 표현하는 성질을 가지지 않은 형용사

• 예 (단음절)monosyllabic heterological

(다음절)polysyllabic ￢ heterological

• 그러나 Heterological ???

• p ⇔ ￢ p.

– Gödel의 불완전성 두 번째 정리(첫 번째 정리의 corollary).

– 큰일 났다!

• 그런데, 이거 모두 말장난(논리장난) 아닌가?

– 맞다()

서양 과학과 동양 인문학

• 서양 과학

– 수학 또는 과학

• F = ma.

• E = mc2.

– 19c말 – 20c초, 쉬운 과학과 공학을 이용한 무력으로 세계제패.

• 경제적 우월성

– 과학 또는 수학은 쉽다.

– 공학은 어렵다.

• 자연과 사람의 문제.

– Cantor, Russell, Gödel, Hilbert, ...

• 형식주의, 논리주의의 붕괴

• 과학(수학) 만능에 대한 수학자들의 경고.

• 동양 인문학

– 사람에 대한 이해와 존경

– 사람이 제일 어렵다.

• 미래의 전산학

– 사람의 문제를 다룬다.

– 기존의 공학과는 전혀 다른 새로운 학문이다.

– 프로그램학

• SIGPL

집합 곱(Cartesian product)

• 집합 A와 집합 B의 집합곱:

A ⅹ B = {(a, b)| a ∈ A, b ∈ B}.

순서쌍(ordered pair)들의 집합: (a, b) ∈ A ⅹ B.

• 관계(relation): R ⊆ A ⅹ B

– 집합 A(정의역, domain)에서 집합 B(치역, range, codomain)로 가는

이진관계(binary relation)

– 두 가지 표현 방법

• 집합 (a, b) ∈ R

• 이진관계 a R b

– 예: a = b, a ≥ b, A → α, …

– |R| = 

• 함수: f: A → B

– 정의역이 A이고 치역이 B인 함수 f

• 특수한(두 가지 조건) 이진관계

• ∀a ∈ A, ∃1b b ∈ B, a R b.

• 전체(total) 함수, 유일성(uniqueness)

– |f| = 

– 세 번째 표현 방법(유일성)

• 함수 f(a) = b, f a = b, λa.b, … .

– f: A1 ⅹ A2 ⅹ … ⅹ An → B1 ⅹ B2 ⅹ … ⅹ Bm.

f(a1, a2, … , an) = (b1 , b2, … , bm).

관계(함수) 곱

• R1 ⊆ A ⅹ B이고 R2 ⊆ B ⅹ C이면 

관계(함수)곱(composition)

R1 ∙ R2 = {(a, c)| a R1 b, b R2 c}.

• R ⊆ A ⅹ A

– 집합 A에 관한(on) 관계(relation)

– R2 = R ∙ R.

• 반복 곱(repeated composition): Rn의 재귀적(recursive)정의(n ≥ 1)

R1 = R n = 1,

Rn = Rn-1 ∙ R n ≥ 2.

• idA = {(a, a)| a ∈ A} 항등원(identity)

– ∀R ⊆ A ⅹ A, idA ∙ R = R ∙ idA = R. 

• 반복 곱의 확장(n ≥ 0)

R0 = idA n = 0,

Rn = Rn-1 ∙ R n ≥ 1.

• 반복 곱의 합(closure) R*와 R†의 정의

R† = R1 ∪ R2 ∪ R3 ∪ … 

R* = R0 ∪ R1 ∪ R2 ∪ … 

• R ⊆ R† ⊆ R*.

한글 모아쓰기 기계

(오토마타) 

한국과학원(KAIS)

석사학위논문, 1978. 2.

최광무

현대한글 정의

• 초성 19 자 = 자음 14 자 + 겹자음 5 자

ㄱ, ㄴ, ㄷ, ㄹ, ㅁ, ㅂ, ㅅ, ㅇ, ㅈ, ㅊ, ㅋ, ㅍ, ㅍ, ㅎ,

ㄲ, ㄸ, ㅃ, ㅆ, ㅉ

• 중성 21 자 = 모음 10 자 + 겹모음 11 자

ㅏ, ㅑ, ㅓ, ㅕ, ㅗ, ㅛ, ㅜ, ㅠ, ㅡ, ㅣ

                  ㅘ,     ㅝ,

                  ㅙ,     ㅞ,

ㅐ, ㅒ, ㅔ, ㅖ, ㅚ,     ㅟ,      ㅢ,

• 받침 28 자 = 자음 14 자 + 겹자음 2 자 + 복자음 11자 + 

ㄱ, ㄴ, ㄷ, ㄹ, ㅁ, ㅂ, ㅅ, ㅇ, ㅈ, ㅊ, ㅋ, ㅌ, ㅍ, ㅎ.

ㄲ,                       ㅆ,

ㄳ, ㄵ,      ㄺ,     ㅄ,

ㄶ,      ㄻ,

              ㄼ, ㄽ, ㄾ, ㄿ, ㅀ,

 받침없는경우

• 한글 = 초성ⅹ중성ⅹ받침 = 19 ⅹ 21 ⅹ 28 = 1,1172자

– 한글 unicode

한글 기본자모

• 기본자모 24자

– 자음 14자, 모음 10자

– ㄱ ㅏ ㄱ ㄱ ㄱ ㅗ = 각꼬 or 갂고

• ㄱ과 ㄲ을 다른 문자로 한다.

• 글자 끝 기호 필요.

• 표준 기본자모(29자)

– 자음 14자 + 모음 10자 + 쌍자음 5자(ㄲ, ㄸ, ㅃ, ㅆ, ㅉ)

• 최소 기본자모(26자)

– 자음 14자 + 모음 10자 + 쌍자음 2자(ㄲ, ㅆ)

• 현재 컴퓨터 자판(33자)

– 자음 14자 + 모음 14자(ㅐ, ㅒ, ㅔ, ㅖ) + 쌍자음 5자

• 3ⅹ4 자판

– 삼성: 11자 = 모음 3자 + 자음 7자 + Blank(시간초과; 글자 끝)

• 모음 3자: ∙ (천), ㅡ(지), ㅣ(인)

• 자음 7자: ㄱ(ㅋ, ㄲ), ㄴ,(ㄹ), ㄷ(ㅌ,ㄸ), ㅂ(ㅍ, ㅃ), ㅅ(ㅎ, ㅆ), ㅈ,(ㅊ, ㅉ), ㅇ(ㅁ)

– LG: 12자 = 모음 4자 + 자음 6자 + 획 추가 + 쌍 자음

• 모음 4자:ㅏ, ㅓ, ㅡ, ㅣ

• 자음 6자: ㄱ(ㅋ), ㄴ(ㄷ, ㅌ), ㄹ, ㅁ(ㅂ, ㅍ), ㅅ(ㅈ, ㅊ), ㅇ(ㅎ)

한글 모아쓰기기계(29자)

기본자모 24자 + 겹자음 5자

한글의 출력

9벌식

• 9벌식(출력 벌수(타자기)) 한글 (11x15)

– 초성 6가지/초성 ⅹ 19 초성 = 114 가지

• 가형 초성 ㄱ: 가, 갸, 거, 겨, 개, 걔, 게, 계, 기

• 고형 초성 ㄱ: 고, 교, 구, 규, 그

• 과형 초성 ㄱ: 과, 괘, 괴, 궈, 궤, 귀, 긔

• 각형 초성 ㄱ: 각, 갹, 걱, 격, 객, 걕, 겍, 곅, 기

• 곡형 초성 ㄱ: 곡, 굑, 국, 귝, 극

• 곽형 초성 ㄱ: 곽, 괙, 괵, 궉, 궥, 귁, 긕

– 중성 2가지/중성 ⅹ 21 중성 =   42 가지

• 받침 O: 아, 야, 어, 여, 오, 요, 우, 유, 으, 이, 애, 얘, 에, 예, 의, 와, 왜, 외, 워, 웨, 위

• 받침 X: 악, 약, 억, 역, 옥, 욕, 욱, 육, 윽, 익, 액, 얙, 엑, 옉, 읙, 왁, 왝, 왹, 웍, 웩, 윅

– 받침 1가지/받침 ⅹ 27 받침(ε 제외) =   27 가지

• 한글 dot matrix printer

– Printronix, 150 d.p.i.

– 183 가지 x 11 x 15 / 8 ≒ 3.7 KB

• Hoffman coding

• 1 KB + 0.5 KB

– 한글 모아쓰기 기계 0.5 KB(Intel 8080)

– 2KB ROM

한글 모아쓰기기계(33자)

컴퓨터 자판

거꾸로, 앞에서(prefix), 뒤에서(postfix),

Firstk, Followk.

• 거꾸로: 〈∙〉R: V* → V*.

(X1X2 … Xn)R = XnXn-1 … X1.

• 앞에서(Prefix) k개: k:〈∙〉: N ⅹ V* → V≤k. k ∈ N, X1X2 … Xn ∈ V*(n≥0).

k:X1X2 … Xn = X1X2 … Xk, (k ≤ n 이면)

   = X1X2 … Xn. (k ≥ n 이면)

• 뒤에서(Postfix) k개: 〈∙〉:k: N ⅹ V* → V≤k. α ∈ V*, k ∈ N.

α:k = (k:αR)R.

• 예

– 겨울학교R = 교학울겨.

– 2:겨울학교 = 겨울.

– 겨울학교:3 = 울학교.

– 5:겨울학교 = 겨울학교:5 = 겨울학교.

• 문법 G = (N, Σ, P, S)에서

• Firstk(∙): V* → Σ≤k. k ∈ N, α ∈ V*일 때,

Firstk(α) = {k:x ∈ Σ≤k | α ⇒* x ∈ Σ*}

• Followk(∙): N → Σ≤k. k ∈ N, A ∈ N일 때,

Followk(A) = {k:z ∈ Σ≤k | S ⇒* xAz, x, z ∈ Σ*}

유한집합의 같음과 무한집합의 같음

• (유한)집합 A, B의 같음.

– A = B ⇔ A ⊆ B ∧ A ⊇ B.

• 집합 A, B의 함수 f를 통한 같음.

– A =f B ⇔ A →f B ∧ A ←f-1 B ⇔ A ↔f B.

• ∀a ∈ A, ∃1f(a) ∈ B ∧ ∀b ∈ B, ∃1f-1(b) ∈ A.

– 무한집합 A, B의 같음(=f).

– 비록 A ⊂ B이어도 A ↔f B ⇔ A =f B.

– = ⊂ =f

• 강한 같음과 약한 같음.

• A ↔f B ⇔ |A| = |B| ⇔ A =f B.

– {0, 1, 2} ↔f {a, b, c} ↔f {사과, 배, 감}

– 자연수0 ↔f 자연수1 ↔f 짝수 ↔f 홀수 ↔f 정수

↔f 유리수 ⊆ 자연수 X 자연수 = 자연수2 

↔f 자연수k.

– ↔f ⇔ ↔.

– =f ?= =.

강한(stronger) 조건

• 조건(condition, predicate)과 진리집합(truth set)

– 조건 p: U → {true, false}를 만족하는,

– 진리집합 P = {x ∈ U| p(x)}.

• 조건 p가 조건 q보다 강(stronger)하다.

– p ⇒ q ≡ P ⊆ Q.

– p가 사실이면, q는 충분히 사실이다.

• 조건 q가 조건 p보다 약(weaker)하다.

– q ← p ≡ Q ⊇ P.

– p가 사실이면, q는 사실일 필요가 있다.

• S(trong)LL(k) ⇒ LL(k)

– SLL(k) 문법이 LL(k) 문법보다 더 적고,

– SLL(k) 언어가 LL(k) 언어보다 더 적다.

• 약한 LL(k)파서가 강한 SLL(k) 파서보다 더 많은 문법을 결정적으로 해결한다.

 

•  

파서 결정성과 문법 애매성

• 문법의 애매성(ambiguity)

– 같은 문장에 파스나무가 두 개 이상이면 애매한 문법이다.

– 애매하지 않은 문법은 명백하다 한다.

• 파서가 같은 상황에서 행동을 두 개 이상 가지면 비결정적이다.

• 파서 결정성과 문법 애매성

– 파서가 결정적이면 문법은 명백하다.

– 문법이 애매하면 파서는 비결정적이다.(대우)

– 문법이 명백하면 파서는 비결정적인가?(역)

• 그때 그때 다르다.

• 모든 문법의 오른/왼 파서는 비결정적이다.

• 왼 재귀문법의 SLL(k), LL(k)파서는 비결정적이다.

• 모든 명백한 문법의 LR(k)파서는 결정적인가?

– ???

같은관계(equivalence relation)

• R ⊆ A ⅹ A일 때, R이

– reflexive: ∀a ∈ A, a R a,

– symmetric: a R b ⇒ b R a,

– transitive: a R b ∧ b R c ⇒ a R c 이면

• R은 같은관계(equivalence relation)라고 한다.

• R이 같은관계이면, R의 같은부류(equivalent class)들이 집합 A를 완전히 나눈다(partition)고 한다.

• R의 같은부류: a ∈ A, [a]R = {b| a R b}.

– 같은부류도 집합이다.([a]R ⊆ A)

• 집합 A의 완전한 나눔: ParR(A) = {[a]R| a ∈ A}.

– a R b ⇔ [a]R = [b]R.

– a ￢Rb ⇔ [a]R ∩ [b]R = ø. 서로 소(disjoint)

– ∪a ∈ A [a]R = A. 전 집합(universe)

• 두 집합 A, B의 관계

– A = B.

• A ⊂ B..

• A ⊆ B.

– A ∩ B = Φ.

– 나머지 경우.

• 벤다이어 그램 

Dijkstra의 mini-language

• 〈문장〉 → abort | skip

| x1, x2, …, xn := E1, E2, …, En 

| 〈문장〉 ; 〈문장〉

| if B1 → SL1 | B2 → SL2 | … | Bn → SLn fi

| do B1 → SL1 | B2 → SL2 | … | Bn → SLn od.

• 동시 배정(concurrent assignment)

– x, y := y, x

• x = old(y) ∧ y = old(x)

– x := y; y := x

• x = old(y) ∧ y = old(y) ⇔ x := y; skip.

– y := x; x := y

• y = old(x) ∧ x = old(x) ⇔ y := x; skip.

• 비결정적(nondeterministic)으로 가드(guard)를 선택한다.

– True인 가드(Bk 또는 Bm)가 둘 이상이면 그 중 아무나(nondeterministic) 선택한다.

• if x ≥ y → m := x | x ≤ y → m := y fi

(m = x ∨ m = y) ∧ (m ≥ x) ∧ (m ≥ y).

• if-fi 구조에서 true인 가드가 하나도 없으면 abort이다.

– if fi ⇔ abort.

Loop invariance와 terminating 조건 

• do-od 구조는 true인 가드가 없으면 loop이 끝난다.

– do-od ⇔ skip.

• 간단한 do-od 프로그램.

q1, q2, q3, q4 := Q1, Q2, Q3, Q4;

do q1 > q2 → q1, q2 := q2, q1 

  | q2 > q3 → q2, q3 := q3, q2 

  | q3 > q4 → q3, q4 := q4, q3 

od

• do-od 프로그램이 끝나고 나면,

– ￢(q1 > q2) ∧ ￢(q2 > q3) ∧ ￢(q3 > q4)

– (q1 ≤ q2) ∧ (q2 ≤ q3) ∧ (q3 ≤ q4)

– q1 ≤ q2 ≤ q3 ≤ q4.

• s := 0; for i:=1 to 100 do s := s + i od

• Loop invariance condition

– Loop 시작 직전

• Initialize

– Loop 탈출 test 할때

• Update

– Loop을 나와서도 만족한다.

• After termination

• Loop termination condition

– Loop을 한 번 돌 때 마다 반드시 감소(단조감소; monotonically decreasing)하는 양 함수

산수, 논리함수는 기본재귀다.

• 산수함수

• 상수(constant) Kn: N → N({n}).

– Kn(x) = σ(σ(…(σ(ζ(x)))…)) = ζ°σn(x) = n.

• 더하기: +: N ⅹ N → N.

– +(n, ζ(m) = Km. n + ζ(m) = Km.   n + 0 = Km.

– +(n, σ(m)) = σ(+(n, m). n + σ(m) = σ(n + m).   n + (m+1) = (n + m)+1.

• 곱하기: ∙ : N ⅹ N → N. 거듭곱: ^: N ⅹ N → N.

– n∙0 =0. n^0 = 1.

– n∙(m+1) = n∙m + m n^(m+1) = (n^m)∙n

• 앞수: σ-1: N → N. σ-1(n) = n – 1, if n > 0; 0, if n=0.

• 자연수빼기: ↓: N ⅹ N → N. m↓n = m – n, if m ≥ n, 0, if m ≤ n.

• 나누기: ÷, mod: N ⅹ N → N.

• 논리함수

• 같은가?: =: N ⅹ N → {0, 1} (n = m) = (1↓((n↓m) + (m↓n))).

– ≠, >, <. ≥, ≤: N ⅹ N → {0, 1}

• ∧, ∨: {0. 1} ⅹ {0, 1} → {0, 1}. ¬: {0, 1} → {0, 1}.

TM은 μ-재귀 부분함수다.

• TM의 상황 (α, p, β) ↔ (w, p, n)

• α, β ∈ Γ*, p ∈ Q, w, p, n ∈ N.

• w = #|Γ|(αβ)R, p ∈ {0, …, |Q|-1}, n ∈ {1, …, |αβ|},

단 qs = 1, qf = 0, 현재 n = |α|+1.

• 1:β = (w÷bn-1)↓(b∙(w÷bn))

• step: N3 → N3: (w, p, n) → (w’, p’, n’).

– 기본재귀함수.

• run: N3ⅹ N → N3:

– run(w, p, n, 0) = (w, p, n)

– run(w, p, n, t+1) = step(run(w, p, n, t))

기본재귀함수.

• stoptime(w) = μ t [π23(w, 1, 1) = 0]

– stoptime은 μ-재귀 부분함수다.

• fTM(w) = π13(run(w, 1, 1, stoptime(w)).

– fTM도 μ-재귀 부분함수다.

무한이진수

자연수의 멱 집합(power set)

• 집합 Σ에서 정의된 길이가 n인 문자열 Σn.

– s: {1, 2, …, n} →  Σ.

– 예: d3: {1, 2, 3} → {0, 1, 2, …, 9}.

• “203”: d3(1) = 2, d3(2) = 0, d3(3) = 3.

• |d3| = 103 = 1000.

– |Σn| = |Σ|n.

• 무한이진수 2N.

– 2N: N → {0, 1} |b| = 2|N|.

• 집합 A의 멱 집합(Power sets)

– P(A) = 2A = {B ⊆ A}

– |P(A)| = 2|A|.

• 자연수의 멱 집합 ↔ 무한이진수.

– P(N) ↔ (N → {0, 1})

– ∴ |P(N)| = 2|N|.

• |N| =f |Nk| > |2N|.

– |N| ⅹ |N| ⅹ … ⅹ |N| > 2 ⅹ 2 ⅹ …

– Cantor의 대각선화 주장(diagonal argument)