언어, 문법, 기계, 파서, 고쳐쓰기, 현대수학의 한계, 그리고 미래의 전산학 SIGPL 겨울학교 2012. 2. 3. 최광무 한국과학기술원 전산학과

차례 언어이론의 기초 Regular 언어(language) Rewriting System 혹은 파서 한글 모아쓰기 기계(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)과 같은 문제들 끝내기 이야기 유클리드 기하학 - 증명의 아름다움 피타고라스 – 무리수 미분이 이상하다? 미분을 완전히 그리고 적절히 정의하였는가? SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

언어(Languages) – 소통수단 인문사회과학 예술 자연과학, 공학, 전산학 철학, 역사, 사회학, 경제, 법률 모국어(자연언어) 애매(Ambiguous)하다 복잡하다 영어강의 ??? 예술 음악, 미술, 스포츠 연주, 형태, 행동 자연과학, 공학, 전산학 수학 엄밀 (Rigorous, Formal) 하다 간단하다 전산학 프로그래밍 언어 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

구문론(構文論; Syntax) 4개의 전문용어(terminology) 언어와 어휘, 문자열의 예 한글 모아쓰기 오토마타 어휘(vocabulary, alphabet), Σ 기본문자들의 집합 언어의 axiomS(atom) 문자(symbol) a ∈ Σ. 어휘의 원소 문자열(string) x ∈ Σ ∗ . 문자(symbol)들이 줄 선(sequence) 것 문자열(수열) 언어(language) L ⊆ Σ ∗ . 문장(문자열)들의 집합 언어와 어휘, 문자열의 예 이진수 Σ = {0, 1} 2자 십진수 Σ = {0, 1, 2, …, 9} 10자 한글 Σ = {ㄱ, ㄴ, …, ㅎ, ㅏ, ㅑ, …, ㅣ} 24자 ㄱ ㅕㅇㅜㄹㅎㅏㄱㄱㅛ 영어 Σ = {a, b, …, z} 26자 Winter School 컴퓨터 Unicode 겨울학교 한글 모아쓰기 오토마타 한글 모아쓰기 기계 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

전문용어 4개+ ε 빈 문자열(empty string) Σ 0 = {ε} Σ = Σ 1 = {0, 1} 산수에 +에서 0이나 ⅹ에서 1과 같은 항등원(identity) Σ 0 = {ε} Σ = Σ 1 = {0, 1} Σ 2 = {00, 01, 10, 11} … Σ 𝑛 = {x∈{0, 1}∗ | |x| = n} Σ ∗ = Σ 0 ∪ Σ 1 ∪ Σ 2 ∪ … 문자열의 universe(전 집합) Σ가 많이 있다. 4개의 전문용어 문자(symbol) a ∈ Σ 어휘(vocabulary) Σ 문자열(string) x ∈ Σ ∗ 언어(language) L ⊆ Σ ∗ 언어의 문장(statement)확인문제(membership problem) 문자열 x ∈ Σ ∗ 가 문장(x ∈ L)인가, 아닌가(x ￢∈ L). 기계(automata) Σ ∗ • y ∈ Σ ∗ ¬∈L L • x ∈ Σ ∗ ∈L Σ† = Σ 1 ∪ Σ 2 ∪ Σ 3 ∪ … Σ • a∈Σ Σ† = Σ ∗ / {ε}, Σ ∗ = Σ† ∪ {ε}. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

문법(Grammar) 예 “x = 5”라는 문장에 필요한 문법규칙 문법 G = (N, Σ, P, S)의 요소 4개 <문> → <좌> “=“ <우> <좌> → “x” | … <우> → “5” | … 문법 G = (N, Σ, P, S)의 요소 4개 N: 넌 터미널(Nonterminal symbolS), 단 V = N ∪ Σ. N = {<문>, <좌>, <우>} Σ: 터미널(Terminal symbolS) Σ = {“x”, “=“, “5”} S: 시작 문자(Start symbol) S ∈ N, S = <문> P: 규칙(Production ruleS) P ⊆ N x (N∪Σ)*. (A, α) ∈ P일 때, A → α ∈ P 또는 A → α로 쓴다. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

문법 G = (N, Σ, P, S)과 유도, 언어 <문> <좌> “=” <우> “x” “5” 유도(derivation), ⇒ A → α ∈ P 일 때, 임의의 β, γ ∈ V*에 대하여, 단 V* = (N∪Σ)*. βAγ ⇒A→α βαγ. ⇒ ⊆ V* ⅹ V*. → ⊆ ⇒. →는 유한, ⇒는 무한. 유도의 확장: ⇒n, ⇒*. ⇒0 = idV*. {α ⇒0 α| α ∈ V*} ⇒n = ⇒n-1 ∙ ⇒ n ≥ 1. ⇒* = ⇒0 ∪ ⇒ 1 ∪ ⇒ 2 ∪ … 언어, L(G): 문법 G가 정의한 언어 L(G) L(G) = {w ∈ T* | S ⇒* w}. 예: <문> ⇒ <좌> “=“ <우> ⇒ “x” “=“ <우> ⇒ “x” “=“ “5” <문> <좌> “=” <우> “x” “5” SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

문법의 계층(hierarchical)구조 Type 3: 정규(regular) 문법 A → xB, A → y. A, B ∈ N, x, y ∈ Σ*. 오른 줄(right linear) (정규)문법 A → aB, A → b. A, B ∈ N, a, b ∈ Σ. 오른 줄 (정규)문법의 normal form A → Bx, A → y. A, B ∈ N, x, y ∈ Σ*. 왼 줄(left linear) (정규)문법 오른 줄 (정규)문법 ⇔ 왼 줄 (정규)문법 x1x2…xnyn ↔ ynxnxn-1…x1. 줄(linear) 구조. 줄(linear list) Type 2: 문맥자유(context-free) 문법 A → α. A ∈ N, α ∈ V* = (N∪Σ)*. A → BC, A → a except S → ε. A, B, C ∈ N, a ∈ Σ. 문맥자유 문법의 normal form Chomsky’s normal form(CNF) 계층(hierarchical) 구조 나무(tree) Type 1: 문맥민감(context-sensitive; recursive) 문법 βAγ → βαγ, A →β:γ α. A ∈ N, α ∈ V†, β, γ ∈ V*. α → β. α ∈ V†, β ∈ V*, |α| ≤ |β|. Type 0: unrestricted 문법 α → β. α ∈ V†, β ∈ V*. S S A1 x1 β S B y γ z α x A1 x1 A2 x2 A2 x2 … … An-1 An-1 An xn An xn yn yn 문법의 계층구조 문법 CSG CFG RG SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

기계(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). 프로그램 TM PDA FA 언어(문제)의 계층구조 프로그램 할 수 없다 프로그램 알고리즘 문맥자유 문제가 아니다. 정규 수학의 대상이 아니다. Cantor, Russell, Gödel, Hilbert, … SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

언어와 문법의 예(1) Type 3: 정규 언어 Type 2: 문맥자유 언어 a b ε A B a b b A B L3 = { anbm | n, m ≥ 0 }. 정규식(regular expression) a*b*. 합(union), 곱(concatenation), 반복곱의 합(closure; *). 더하기, 붙이기, 많이 유한상태기계(FA) Nondeterministic Deterministic 한글모아쓰기기계(automata) 정규문법: G3N: A → aA | B | ε, B → bB | ε. Type 2: 문맥자유 언어 L2n = { anbn | n ≥ 0 }. L2n ⊆ L3. G2n: S → aSb | ε. L2= = { x ∈ {a, b}* | |x|b = |x|a }. L2= ⊆ L2n. G2=: S → aSbS | bSaS | ε. L(G2=) ⊆ L2=, L2= ⊆? L(G2=). Lk,m = {x ∈ {a, b}* | |x|b = k∙|x|a + m}. Gk,m? a b ε A B a b b A B G3D: A → aA | bB | ε, B → bB | ε. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

언어와 문법의 예(2) Type 1: 문맥민감 언어 Type 1: recursive 언어 Type 0: 언어 L13 = { anbncn | n ≥ 0}. G13: S → aSBC | aBC | ε. CB → HB, HB → HC, HC → BC, aB → ab, bB → bb, bC → bc, cC → cc. S ⇒S→aSBCn-1 an-1S(BC)n-1 ⇒S→aBC an(BC)n = anB(CB)n-1C (⇒CB→HB∙HB→HC∙HC→BC)¹/₂n(n-1) anBnCn ⇒aB→ab anbBn-1Cn ⇒bB→bbn-1 anbnCn ⇒bC→bc anbncCn-1 ⇒cC→ccn-1 anbncn. Type 1: recursive 언어 L1xx = { xx| x ∈ {a, b}* }. G1xx: S → aAS | bBS | T Aa → aA, Ba → aB, Ab → bA, Bb → bB, BT → Tb, AT → Ta, T → ε. S ⇒S→aAS|bBSn (aA|bB)nS ⇒S→T (aA|bB)nT ⇒Aa→aA|Ba→aB|Ab→bA|Bb→bBn (a|b)n(A|B)nT ⇒BT→Tb|AT→Tan (a|b)nT(a|b)n ⇒T→ε (a|b)n(a|b)n. Type 0: 언어 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

고쳐쓰기(Rewriting system) 고쳐쓰기 R = (C, →, ι, Φ) C: 고쳐쓰기 상황(ConfigurationS) → ⊆ C ⅹ C. α → β, α, β ∈ C. ι: 처음 상황(initial configuration) ι ∈ C. Φ: 끝 상황(final configurationS) Φ ⊆ C. 유도(derivation), ⇒ α → β 일 때, 임의의 γ, δ ∈ C에 대하여 γAδ ⇒α→β γβδ. →, ⇒, ⇒* ⊆ C ⅹ C. 고쳐쓰기의 정상적인 마침. ι ⇒* φ ∈ Φ. 문법 고쳐쓰기 문장을 만들어가는 고쳐쓰기 생성문법(generative grammar) 문법 G = (N, Σ, P, S)의 고쳐쓰기 RG = ((N ∪ Σ)*, →G = P, S, Σ*). L(RG) = {w ∈ Σ* (= Φ)| ι = S ⇒ 𝐺 ∗ w ∈ Σ*(= Φ)} = L(G). 기계 고쳐쓰기 문장을 없애가며 확인하는 고쳐쓰기(문장확인기계) 기계 M 의 고쳐쓰기 RM = (C ⅹ Σ*, →M, (ci, w), {(cF, ε)}). C: 고쳐쓰기(기계) 상황 Σ*: 나머지 입력문자열 L(RM) = {w ∈ Σ* | ι = (ci, w) ⇒ 𝐴 ∗ (cF, ε) ∈ Φ}. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

정규문법, 문장확인 유한상태기계, 그리고 고쳐쓰기 정규 문법 G3 = (N, Σ, P, S). 유한상태기계 A = (Q, Σ, δ, qS, F). 기계 A의 고쳐쓰기 상황(configurationS) 기계의 상태(stateS) Q ⅹ 나머지 입력문자열 Σ*. 문법 G3를 위한 고쳐쓰기 RA = (Q ⅹ Σ*, →A, (qs, w), {(qf, ε)| qf ∈ F}). qB ∈ δ(qA, y) ⇔ (qA, y) →𝐴(qA, y)→(qB, ε) (qB, ε) ⇔ A → yB ∈ P. 유한상태기계 A ⇔ (정규)고쳐쓰기 RA. ⇔ 정규문법 G3. S S ⇒* xA ⇒A→yB xyB ⇒* xyz. A qF ∈ F. B δ *( , z) δ( , y) δ*( , x) qS = δ *( , z) δ( , y) qA = δ *( , z) qB = qF. x … y z … x y z qS qA qB qF (qS, xyz) (qA, yz) (qB, z) (qF, ε) (qS, xyz) ⇒ 𝐴 ∗ (qA, yz) ⇒𝐴(qA, y)→(qB, ε) (qB, z) (qF, ε) qF ∈ F. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

문맥자유문법 유도 파스(parse) 나무(tree) A → α, A ∈ N, α ∈ V* = (N∪Σ)*. 문맥자유문법의 문자의 구분 N: 터미널이 아닌(nonterminal) 문자 바꿀 문자. T: 터미널(terminal) 문자 바꾼 문자. 유도과정에서 바꿀 문자가 여럿 나온다. 파스(parse)나무(tree) 나무에는 가지(subtree)가 있다. 시작(subroot)이 바꿀 문자 끝(leaf)이 바꾼 문자 계층적(hierarchical) 구조(structure). 문맥자유문법 고치기(유도)의 일반 꼴 S ⇒∗ x0A1x1A2x2 … xn-1Anxn 0 ≤ ∀k ≤ n: xk ∈ Σ*, 1 ≤ ∀k ≤ n: Ak ∈ N, A1, Ak, …, An 중 어떤 문자를 먼저 바꾸어도 나무는 같다. 무엇이 파스나무를 다르게 하는가? 바꿀 문자가 가진 문법 규칙에서 우변 고르기 A → α | β. Nondeterministic S x0 xn Ak ⇒∗ yk ∈ Σ*. … xk-1 x1 A1 Ak … xk xn-1 An y1 yk yn ⇒∗ x0y1x1y2x2 … xn-1ynxn∈ Σ*. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

문맥자유문법의 두 가지 고치기 순서 (⇒𝑙𝑚 /⇒𝑟𝑚) S 문장 구하기의 두 가지 고치기 순서 왼쪽부터 고치기(Leftmost derivation) 오른쪽부터 고치기(Rightmost derivation) 왼쪽부터 고치기(⇒𝑙𝑚 ) S ⇒ 𝑙𝑚 ∗ xBγ x∈Σ*, γ∈V*, B∈N, 오른쪽부터 고치기(⇒𝑟𝑚) S ⇒ 𝑟𝑚 ∗ αBz α∈V*, z∈Σ*, B∈N, 고치기 순서에 따른 두 가지 기계 고치기 순서가 달라도 결과나무는 같다. 왼 파서(Left parser) 왼쪽부터 고치며, 위에서 아래로(top-down) 나무 만들기(parsing). 오른 파서(Right parser) 오른쪽부터 고치기를 거꾸로 하며, 아래서 위로(bottom-up) 나무 만들기. x B γ β y z ⇒ 𝑙𝑚 𝐵→β xβγ ⇒ 𝑙𝑚 ∗ xyγ ⇒ 𝑙𝑚 ∗ xyz ∈ Σ*. B → β, β ⇒ 𝑙𝑚 ∗ y ∈ Σ*, γ ⇒ 𝑙𝑚 ∗ z ∈ Σ*. S ⇒ 𝑟𝑚 𝐵→β αβz ⇒ 𝑟𝑚 ∗ αyz ⇒ 𝑟𝑚 ∗ xyz ∈ Σ*. α B z B → β, β ⇒ 𝑟𝑚 ∗ y ∈ Σ*, α ⇒ 𝑟𝑚 ∗ x ∈ Σ*. β x y SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

왼 유도(⇒𝑙𝑚), 파스나무, Stack, 입력문자열, (Stack, 입력문자열) 시작 문 ⇒𝑙𝑚문→좌=우 좌 = 우 ⇒𝑙𝑚좌→x x = 우 ⇒𝑙𝑚우→5 x = 5 (문, x=5) ⇒문→좌=우 (좌=우, x=5) ⇒좌→x (x=우, x=5) ⇒↓x (=우, =5) ⇒↓= (우, 5) ⇒우→5 (5, 5) ⇒↓5 (ε, ε). 예상한다. 문 확인한다. 좌 x 좌 = 우 = 예상과 확인끝 문 우 5 x 5 위에서 아래로 왼쪽에서 오른쪽으로 나무가 자란다. x = 5 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

왼 파서(→𝐿), 문장확인기계 예상과 확인(Guess and verify) Stack 상황: V* = (N ∪ Σ)*, 단 α ∈ V*, 일 때, stack top이 1:α. 나머지 입력 문자열: Σ*. (1) Stack top이 Y=B ∈ N일 때: S ⇒ 𝑙𝑚 ∗ xBγ ⇒𝑙𝑚 xβγ ⇒ 𝑙𝑚 ∗ xyγ ⇒ 𝑙𝑚 ∗ xyz •S ⇒ 𝐿𝑚 ∗ x•Bγ ⇒ 𝐿𝑚 𝐵→β x•βγ ⇒ 𝐿𝑚 ∗ xy•γ ⇒ 𝐿𝑚 ∗ xyz• (S, xyz) ⇒ 𝐿 ∗ (Bγ, yz) ⇒ 𝐿 (𝐵, ε)→(β, ε) (βγ, yz) ⇒ 𝐿 ∗ (γ, z) ⇒ 𝐿 ∗ (ε, ε) B → β를 선택(nondeterministic)하여 B를 β로 예상한다. Stack에서 B를 pop하고 β를 push. (B, ε) → 𝐿 𝐵→β (β, ε). B를 β로 예상 Guess(Produce) A as α. (2) Stack top이 Y=a=y ∈ Σ일 때: S ⇒ 𝑙𝑚 ∗ xaγ =(⇒ 𝑙𝑚 0 ) xyγ ⇒ 𝑙𝑚 ∗ xyz •S ⇒ 𝐿𝑚 ∗ x•aγ ⇒ 𝐿𝑚 𝑚𝑜𝑣𝑒 • xa•γ = xy•γ ⇒ 𝐿𝑚 ∗ xyz• (S, xyz) ⇒ 𝐿 ∗ (aγ, az) ⇒ 𝐿 (𝑎, 𝑎)→(ε, ε) (= ⇒ 𝐿 ↓𝑎 ) (γ, z) ⇒ 𝐿 ∗ (ε, ε) Stack top a가 현재입력문자 a와 같은가를 확인. Stack에서 a를 pop하고 입력문자열에서도 a를 제거. ↓ (a, a) → 𝐿 (𝑎, 𝑎)→(ε, ε) (= → 𝐿 ↓𝑎 (ε, ε)). a를 확인 Verify(shift) a. S B β γ y x z S a = γ y x z SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

왼 파서 - 2 문법 G의 왼 파서 →𝐿 = (V*ⅹΣ*, →𝐿, (S, w), {(ε, ε)}). 첫 상황 ι = (S, w) ∈ V*ⅹΣ*. 끝 상황 Ф = {(ε, ε) ∈ V*ⅹΣ*}. →𝐿 = {(B, ε) →𝐿 (β, ε)| B → β} ∪ {(a, a) →𝐿 (ε, ε)| a ∈ Σ} 왼 파서는 stack이 입력문자열을 유도하는가 예상하고 확인한다. 첫 상황 ⇒ 𝐿 ∗ 끝 상황. (S, w) ⇒ 𝐿 ∗ (ε, ε). 일반 상황 (α, xyz) ⇒ 𝐿 ∗ (Y, z), α ∈ V*, x, y, z ∈ Σ*, Y ∈ N ∪ Σ. 증명 αz ⇒ 𝑙𝑚 ∗ xYz ⇔ (α, xyz) ⇒ 𝐿 ∗ (Y, yz). B → β1 | β2 (β1 ≠ β2)일 때, (B, ε) → 𝐿 𝐵→β1 (β1, ε). (B, ε) → 𝐿 𝐵→β2 (β2, ε). 비결정적(Nondeterministic)이다. 왼 파서는 문맥자유언어의 문장확인문제를 푸는 기계이다. 문맥자유언어의 문장확인문제는 NP이다. 그러나 CYK 알고리즘은 O(n3). 문맥자유언어의 문장확인문제는 P이다. (S, w) ⇒ 𝐿 |π|+|𝑥| (ε, ε) ↔ •S ⇒ 𝐿𝑚 |π|+|𝑥| w• → S ⇒ 𝑙𝑚 |π| . w ∈ Σ*, π ∈ P*. |π| ≤ |π| + |w|. 왼 유도(⇒𝑙𝑚)는 왼 파서(⇒𝐿)의 요약해석(abstract interpretation)이다. 왼 파서(⇒𝐿)와 ⇒𝐿𝑚 은 같다. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

왼 파서의 예상을 예상한다. 결정적(deterministic) SLL(k) 파서 문맥자유문법 G = (N, Σ, P, S)의 왼 파서의 예상 →𝐿 = {(B, ε) →𝐿 (β, ε)| B → β} B → β1 | β2 (β1 ≠ β2). (S, xyz) ⇒ 𝐿 ∗ (Bγ, yz) ⇒𝐿 (β1γ, yz) ⇒ 𝐿 ∗ (γ, z) ⇒ 𝐿 ∗ (ε, ε) B ⇒ β1 ⇒ 𝑙𝑚 ∗ y1 ∈ Σ*, k:y1 ∈ Firstk(β1). (S, xyz) ⇒ 𝐿 ∗ (Bγ, yz) ⇒𝐿 (β2γ, yz) ⇒ 𝐿 ∗ (γ, z) ⇒ 𝐿 ∗ (ε, ε) B ⇒ β2 ⇒ 𝑙𝑚 ∗ y2 ∈ Σ*, k:y2 ∈ Firstk(β2). γ ⇒* z ∈ Σ*, k:z ∈ Followk(B). k:Firstk(β1)∙Followk(B) ∩ k:Firstk(β2)∙Followk(B) = ø이면 결정적. u1 ∈ k:Firstk(β1)∙Followk(B): (B, u1) →SLL(k) (β1, u1) u2 ∈ k:Firstk(β2)∙Followk(B): (B, u2) →SLL(k) (β2, u2) 문법 G의 Strong LL(k) 파서 →SLL(k) = (V*ⅹΣ*, →SLL(k), (S, w), {(ε, ε)}), →SLL(k) = {(B, y) →SLL(k) (β, y)| B → β, y ∈ k:Firstk(β)∙Followk(B)} ∪ {(a, a) →SLL(k) (ε, ε)| a ∈ Σ} 문법 G의 Strong LL(k) 파서가 결정적(deterministic)이면, 문법 G는 SLL(k) 문법이다. Left to right scan with Leftmost derivation using k-lookahead symbols. SLL(1) 문법 ⊆ SLL(k) 문법 ⊆ LL(k) 문법(u1 = k:y1z, u2 = k:y2z). 하지만 k=1인 경우, SLL(1) 문법 = LL(1) 문법. S x B γ β2 β β1 z y1 y2 y 왼파서 (B, ε) →𝐿 (β1, ε) (B, ε) →𝐿 (β2, ε) SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

오른 파서는 오른 유도(⇒𝑟𝑚)를 거꾸로(←𝑟𝑚)한다. 시작 x = 5 ←𝑟𝑚x←좌 좌 = 5 ←𝑟𝑚5←우 좌 = 우 ←𝑟𝑚좌=우←문 문. (ε, x=5) ⇒↑x (x, =5) ⇒ x←좌 (좌, =5) ⇒↑= (=좌, 5) ⇒↑5 (5=좌, ε) ⇒ 5←우 (우=좌, ε) ⇒우=좌←문(문, ε). 저장한다. 문 확인한다. 우 5 좌 = 우 = 저장과 확인끝 문 좌 x x 5 오른쪽에서 왼쪽으로 아래에서 위로 나무가 자란다. (좌=우)R x = 5 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

오른 파서(→𝑅 ) 저장과 확인(Shift and reduce) 오른 파서가 하는 두 가지 행동 Stack에 입력문자 a ∈ Σ를 저장(shift)한다. Stack에서 a를 저장하고 입력문자열에서 a를 제거. (ε, a) → 𝑅 ↑𝑎 (a, ε). a ∈ Σ를 stack에 저장 shift a ∈ Σ. Stack에 A → α의 우변 αR이 있을 때: αR을 A로 확인(reduce)한다. Stack에서 αR을 pop하고 A를 push한다. (αR, ε) → 𝑅 α←𝐴 (A, ε). Stack에 α 를 A 로 확인 reduce α to A. 오른 파서는 입력문자열을 stack에 저장한 후 확인한다. 첫 상황 ⇒ 𝐿 ∗ 끝 상황. (ε, w) ⇒ 𝑅 ∗ (S, ε). 일반 상황 (ε, xyz) ⇒ 𝑅 ∗ (YαR, z), α ∈ V*, x, y, z ∈ Σ*, Y ∈ N ∪ Σ. 증명 αYz ⇒ 𝑟𝑚 ∗ xyz ⇔ (ε, xyz) ⇒ 𝑅 ∗ (YαR, z). 오른 파서의 비결정성(Nondeterminism) Stack에 규칙 A → α의 우변 αR이 있을 때 입력문자열에서 a를 저장(shift)할까, αR을 A로 확인(reduce)할 까? shift-reduce conflict 또 다른 규칙 A’ → α’의 우변 α’R이 있을 때, reduce-reduce conflict S Y α z x y β SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

오른 파서와 LR(1) itemS x = 5 ←𝑟𝑚x←좌 좌 = 5 ←𝑟𝑚5←우 좌 = 우 ←𝑟𝑚좌=우←문 문. [문 → •좌=우, ε] [좌 → •x, =] 시작 x = 5 ←𝑟𝑚x←좌 좌 = 5 ←𝑟𝑚5←우 좌 = 우 ←𝑟𝑚좌=우←문 문. (ε, x=5) ⇒↑x (x, =5) ⇒ x←좌(좌, =5) ⇒↑= (=좌, 5) ⇒↑5 (5=좌, ε) ⇒ 5←우(우=좌, ε) ⇒우=좌←문(문, ε). [좌 → x•, =] [문 → 좌•=우, ε] [문 → 좌=•우, ε] [우 → •5, ε] [우 → 5•, ε] 저장한다. 문 확인한다. [문 → 좌=우•, ε] 우 5 좌 = 우 = [S’ → 문•, ε] 저장과 확인끝 좌 문 x x 5 오른쪽에서 왼쪽으로 아래에서 위로 나무가 자란다. x = 5 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

오른 파서의 비결정성 줄이기 오른 파서 → LR(k) 파서 문자(오른 파서) 대신에 LR(k) state(LR(k) 파서)를 stack에 넣는다. X ∈ N ∪ Σ → [XαR]LR(k) ↔ 〈XαR〉LR(k). Rk = {[B → β1•β2, x]| B→β1β2, x ∈ Σ≤k }: LR(k) itemS. LR(k) itemsS: 〈∙〉k: V* → 2Rk. 〈αβ1〉k = {[B → β1•β2, k:z] | S ⇒ 𝑟𝑚 ∗ αBz ⇒𝑟𝑚 αβ1β2z, B → β1β2} δ1R LR(k)(ρk) δ2R, if 〈δ1〉k = 〈δ2〉k. 오른쪽에 있는 문자를 stack top에 넣으므로 stack 문자열이 뒤집어져(δR) 있다. LR(k)는 집합 V*에 정의된 같은관계이다. 같은부류 [δ]LR(k)를(stack 문자열의 집합) LR(k) state라 한다. [δR]LR(k) ↔ [δR]ρk ↔ [δR]k ↔ 〈[δR]LR(k)〉k ↔ 〈δ〉LR(k) ↔ 〈δ〉ρk ↔ 〈δ〉k. ParLR(k)(V*)를 [V*]LR(k)라고 쓰고 LR(k) state의 집합이다. LR(k) state ↔ LR(k) item의 집합 ↔ stack 문자열의 집합 Stack에 있는 βR←B로 확인할 때, •S ⇒ 𝑅𝑚 ∗ αB•z ⇒𝑹𝒎 αβ•z ⇒ 𝑅𝑚 ∗ αy•z ⇒ 𝑅𝑚 ∗ •xyz. •xyz ←𝑅𝑚 ∗ αy•z ←𝑅𝑚 ∗ αβ•z ←𝑹𝒎 αB•z ←𝑅𝑚 ∗ S•. (ε, xyz) ⇒ 𝑅 ∗ (αR, yz) ⇒ 𝑅 ∗ (βRαR, y2z) ⇒𝑹 (BαR, z) ⇒ 𝑅 ∗ (S, ε). (βR, ε) →𝑅 (B, ε)를 (βRαR, x) →LR(k) (BαR, x), x = k:z로 제한하여 확인한다. [B → β1•β2, x] ∈ 〈αβ1〉LR(k) ↔ [β1RαR]LR(k) 일 때, β2 = ε이면 x를 보고 β1←B로 확인(reduce)한다. 1:β2 ∈ Σ 이면 저장(shift)한다. 1:β2 ∈ N이면 확인을 미리 준비(《∙》)한다. S B α z x y β SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

LR(k) 파서 만들기 《∙》ρk: Rk → 2Rk. 《[B→β1•Aβ2, x]》ρk = {[A→•ξ, y]| A → ξ, y ∈ Firstk(β2x)} [A→ξ•, y] ∈ 〈αβ1ξ〉ρk일 때, y를 보고 ξ←A로 확인할 준비한다. 〈ε〉ρk = 《[S’→•S, ε]》ρk* ∈ [ V ∗ ]LR(k)로 시작(basis). [B→β1•Xβ2, x] ∈ 〈αβ1〉ρk ∈ [ V ∗ ]LR(k)이면(recursion), [B→β1X•β2, x] ∈ 《〈αβ1X〉ρk 》ρk* ∈ [ V ∗ ]LR(k). 〈αβ1X〉ρk = 《[B→β1X•β2, y]》ρk* = {[B→β1X•β2, y]} ∪ 《[B→β1X•β2, y]》ρk†. 단 {[B→β1X•β2, y]} ∪ 《[B→β1X•β2, y]》ρk† = ø. 문법 G = (N, Σ, P, S)의 LR(k) 파서, LRk(G) = (([ V ∗ ]LR(k) ⅹΣ*, →LR(k), (〈ε〉k, w), {(〈ε〉k∙〈S〉k, ε)}). →LR(k) = {(〈αβ1〉k, a) →LR(k) (〈αβ1∙a〉k∙〈αβ1〉k, ε) | a ∈ Σ, [A → β1•aβ2, x] ∈ 〈αβ1〉k} ∪ {(〈αβ1∙ξ〉k∙〈αβ1∙ξ:|ξ|-1〉k∙ … ∙〈αβ1∙ξ:1〉k∙〈αβ1〉k, x) →LR(k) (〈αβ1∙A〉k∙〈αβ1〉k, x) | [B → β1•Aβ2, y] ∈ 〈αβ1〉k, [A → •ξ, x] ∈ 《〈αβ1〉k》k†, [A → ξ•, x] ∈ 〈αβ1ξ〉k, [B → β1A•β2, y] ∈ 〈αβ1A〉k}. S [S’→•S, ε] ∈ 〈ε〉k [S’→S•, ε] ∈ 〈S〉k αβ1 A [B→β1•Aβ2, x] ∈ 〈αβ1〉k [B→β1A•β2, x] ∈ 〈αβ1A〉k [A→•ξ, y] ∈ 《〈αβ1〉k》k† ξ [A→ξ•, y] ∈ 〈αβ1ξ〉k SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

왼 파서의 비결정성 더 줄이기 SLL(k) 파서 → LL(k) 파서 문자(SLL(k) 파서) 대신에 LL(k) state(LL(k) 파서)를 stack에 넣는다. X ∈ N ∪ Σ → [XαR]LR(k) ↔ 〈XαR〉LR(k). Lk = {[B → β1•β2, x]| B→β1β2, x ∈ Σ≤k}: LL(k) itemS. 예상할 때, 올 수 있는 입력 문자열을 SLL(k) 보다 더 자세히 계산한다. LL(k) itemS: 〈∙〉k: V* → 2Lk. 〈β2γ〉k = {[B → β1•β2, x] | S ⇒ 𝑙𝑚 ∗ Bγ ⇒lm xβ1β2γ, B → β1β2, x ∈ Firstk(β2γ)} δ1 LL(k)(λk) δ2, if 〈δ1〉k = 〈δ2〉k. 왼쪽에 있는 문자를 stack top에 넣으므로 stack 문자열이 뒤집히지 않는다. LL(k)는 집합 V*에 정의된 같은관계이다. 같은부류 [δ]LL(k)(stack 문자열들의 집합)를 LL(k) state라 한다. [δ]LL(k) ↔ [δ]λk ↔ [δ]k ↔ 〈[δ]LL(k)〉k ↔ 〈δ〉LL(k) ↔ 〈δ〉λk ↔ 〈δ〉k. ParLL(k)(V*)를 [V*]LL(k) 라고 쓰고 LL(k) state의 집합이다. Stack에 있는 B→β로 예상할 때, •S ⇒ 𝐿𝑚 ∗ x•Bγ ⇒𝑳𝒎 x•βγ ⇒ 𝐿𝑚 ∗ xy•γ ⇒ 𝐿𝑚 ∗ xyz•. (S, xyz) ⇒ 𝐿 ∗ (Bγ, yz) ⇒𝑳 (βγ, yz) ⇒ 𝐿 ∗ (γ, z) ⇒ 𝐿 ∗ (ε, ε). (B, u) →SLL(k) (β, u)에서 u ∈ k:Firstk(β)∙Followk(A)로 예상하나, (B, x) →LL(k) (β, x)에서 x = k:yz로 제한하여 예상한다. {k:yz} ⊆ k:Firstk(β)∙Followk(A). [B → β1•β2, x] ∈ 〈β2γ〉LL(k) ↔ [β2γ]LL(k) 일 때, β1 = ε이면 x를 보고 B→β2로 예상한다. β1:1 ∈ Σ 이면 Σ 이면 확인(verify)한다. β1:1 ∈ N이면 예상을 미리 준비(《∙》)한다. S B β γ y x z SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

LL(k) 파서 만들기 《∙》λk: Lk → 2Lk. 《[B→β1A•β2, x]》λk = {[A→ξ•, x]| A → ξ} [A→•ξ, x] ∈ 〈β2γ〉λk일 때, A→ξ로 예상할 준비한다. 〈ε〉λk = 《[S’→S•, ε]》λk* ∈ [ V ∗ ]LL(k) 로 시작(basis). [B→β1X•β2, x] ∈ 〈β2γ〉λk ∈ [ V ∗ ]LL(k)이면(recursion), [B→β1•Xβ2, y] ∈ 《〈Xβ2γ〉λk》λk* ∈ [ V ∗ ]LL(k), y ∈ Firstk(Xx). 〈Xβ2γ〉λk = 《[B→β1•Xβ2, y]》λk* = {[B→β1•Xβ2, y]} ∪ 《[B→β1•Xβ2, y]》λk†. 단 {[B→β1•Xβ2, y]} ∪ 《[B→β1•Xβ2, y]》λk† = ø. 문법 G = (N, Σ, P, S)의 LL(k) 파서, LLk(G) = (([ V ∗ ]LL(k) ⅹΣ*, →LL(k), ([ε]k∙[S]k, w), {([ε]k, ε)}). →LL(k) = {([A∙β2γ]k∙[γ]k, x) →LL(k) {([ξ∙β2γ]k∙[ξ:|β|-1∙β2γ]k∙ … ∙[ξ:1∙β2γ]k∙[β2γ]k, x) | [B → β1A•β2, y] ∈ 〈β2γ〉k, [A →ξ•, y] ∈ 《〈β2γ〉k》k†, [A → •ξ, x] ∈ 〈β2γ〉k, [B → β1•Aβ2, X] ∈ 〈A∙β2γ〉k}. x ⊆ X. ∪ {([aβ2γ]k∙[γ]k, a) →LL(k) ([β2γ]k, ε) | a ∈ Σ, [A → β1•aβ2, x] ∈ 〈aβ2γ〉k} S [S’→S•, ε] ∈ [ε]k [S’→•S, s] ∈ [S]k β2γ A [B→β1A•β2, x] ∈ [β2γ]k [B→β1•Aβ2, X] ∈ [Aβ2γ]k [A→ξ•, x] ∈ 《[β2γ]k》k† ξ [A→•ξ, y] ∈ [ξβ2γ ]k SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

왼 파서의 종류 유한상태기계 왼 파서 SLL(k) 왼 파서 LL(k) 왼 파서 SLL(k)문법 ⊆ LL(k)문법. A = (Q × Σ ∗ , →A, ( 𝑞 𝑠 , w), {(f, ε)| f∈F}) (q, x) →A (p, ε). 왼 파서 L = (( V ∗ × Σ ∗ ), →L, (S, w), {(ε, ε)}) B를 β로(B → β) 예상(guess B as β) a ∈ Σ를 확인(verify a) (B, ε) →L (β, ε), (a, a) →L (ε, ε). SLL(k) 왼 파서 SLL(k) = (( V ∗ × Σ ∗ ), →SLL(k), (S, w), {(ε, ε)}) (B, x) →SLL(k) (β, x), (a, a) →SLL(k) (ε, ε). x ∈ Firstk(β∙Follwk(B)), LL(k) 왼 파서 LL(k) = (([ V ∗ ]LL(k) × Σ ∗ ), →LL(k), ([ε]k[S]k, w), {([ε]k}, (ε, ε)}) ([B∙γ]k∙[γ]k, x) →LL(k) ([β∙γ]k…[γ]k, x), ([a∙γ]k∙[γ]k, a) →LL(k) [γ]k, ε). [B → •β, x] ∈ 〈β∙γ〉LL(k), [~ → ~•a~, a~] ∈ 〈a∙γ〉LL(k). SLL(k)문법 ⊆ LL(k)문법. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

오른 파서의 종류 오른 파서 LR(k) 오른 파서 LR(k, k) SLR(k) 오른 파서 LR(0, K) K ⊇ k. R = (( V ∗ × Σ ∗ ), →R, (ε, w), {(S, ε)}) a ∈ Σ를 저장(shift a) β를 B로(B → β) 확인(reduce β to B) (ε, a) →R (a, ε); ( β 𝑅 , ε) →R (B, ε) LR(k) 오른 파서 LR(k, k) LR(k) = (([ V ∗ ]LR(k) × Σ ∗ ), →LR(k), ([ε]k, w), {([ε]k∙[S]k}, (ε, ε)}) LR(k) 상태, LR(k) 확인(reduce) ([ α 𝑅 ]k, a) →LR(k) ([ a∙α 𝑅 ]k∙ [α 𝑅 ]k, ε), ([ β 𝑅 ∙ α 𝑅 ]k…[ α 𝑅 ]k, x) →LR(k) ([ Bα 𝑅 ]k∙[ α 𝑅 ]k, x) [~ → ~•a~, a~] ∈ 〈α〉LR(k), [B → β•, x] ∈ 〈αβ〉LR(k). SLR(k) 오른 파서 LR(0, K) K ⊇ k. SLR(k) = (([ V ∗ ]LR(0) × Σ ∗ ), →SLR(k), ([ε]0, w), {([ε]0∙[S]0}, (ε, ε)}) LR(0) 상태, Followk(B) 확인(reduce) ([ α 𝑅 ]0, a) →SLR(k) ([ a∙α 𝑅 ]0∙[ α 𝑅 ]0, ε), ([ β 𝑅 ∙ α 𝑅 ]0…[ α 𝑅 ]0, y) →SLR(k) ([ B∙α 𝑅 ]0∙[ α 𝑅 ]0, y) [~ → ~•a~] ∈ 〈α〉LR(0), [B → β•] ∈ 〈αβ〉LR(0), y ∈ Followk(B). LALR(k) 오른 파서 LR(0, k) LALR(k) = (([ V ∗ ]LR(0) × Σ ∗ ), →LALR(k), ([ε]0, w), {([ε]0∙[S]0}, (ε, ε)}) LR(0) 상태, LR(k) 확인(reduce) ([ α 𝑅 ]0, a) →LALR(k) ([ a∙α 𝑅 ]0∙[ α 𝑅 ]0, ε), ([ β 𝑅 ∙ α 𝑅 ]0…[ α 𝑅 ]0, x) →LALR(k) ([ B∙α 𝑅 ]0∙[ α 𝑅 ]0, x) [~ → ~•a~] ∈ 〈α〉LR(0), [B → β•, x] ∈ 〈αβ〉LR(k). SLR(k)문법 ⊆ LALR(k)문법 ⊆ LR(k)문법. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

LL, RR/LR, RL 파서 LL RR LR RL S S α B B γ β β β S B y γ z α x x y z x y SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

결정적 왼/오른 파서 왼 파서의 결정적 파서 오른 파서의 결정적 파서 왼 파서는 (성실한) 미래학자이고, 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)문법 ⊆ … SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

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은 프로그램이다. 문제(프로그램)의 계층구조 프로그램 할 수 없다 프로그램 알고리즘 NP-complete SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

TM은 프로그램이다 프로그램의 꽃 반복구조(loop)의 문제 항상 끝나는 프로그램(알고리즘) 끝나지 않은 수 도 있는 프로그램 변하지 않는 (loop invariance) 성질 변하는 (loop termination) 성질 반복구조(loop)의 문제 끝나지 않을 수(infinite loop)도 있다 항상 끝나는 프로그램(알고리즘) Type 1 Recursive 전체(total) 함수 끝나지 않은 수 도 있는 프로그램 Type 0 Recursively enumerable 부분(partial) 함수 Recursively enumerable 밖에는 무엇이 있나? 프로그램 할 수 없는 문제들 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

함수와 컴퓨터(프로그램, TM) 문제를 푸는 두 가지 방법 함수 f: Nn → Nm. 부분함수 g: N → N. 해결 방법(operational) 어떻게 하는가(how)? (ε, qs, w) ⇒ 𝑇𝑀 ∗ (α, qf, β). w ∈ Σ*, αβ ∈ Γ*. 함수 문제(functional) 무엇을 하는가(what)? fTM(w) = αβ. 함수 f: Nn → Nm. Nn ↔ N ↔ Nm. f: Nn → Nm. ↔ f’: N → N. 부분함수 g: N → N. ∃x∈ N: [g(x) = X ¬∈N(undefined). 기본재귀함수(primitive recursive) 함수 상수 함수 영(zero) 함수: ζ: N → N({0}). ζ(x) = 0. 다음수(successor) 함수: σ: N → N. σ(n) = n+1. 인수 찾기(projection): πkn: Nn → N. πkn(x) = ak 단 1≤k≤n ∧ x = (a1, …, ak,, … ,an). 기본재귀 f: N ⅹ N → N를 g: N → N와 h: N ⅹ N ⅹ N → N로 정의한다. f(x, ζ(n)) = g(x). f(x, 0) = g(x). f(x, σ(n)) = h(x, n, f(x, n)). f(x, n+1) = h(x, n, f(x, n)). SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

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)이다. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

Cantor의 대각선화 주장(1874; 1891) 비극의 시작 무한이진수 ↔ 자연수(셀 수 있게 무한)이라고 하자. a1 = 00000… a2 = 11111… a3 = 01101… … a = 011 … 대각선화(diagonalization) ￢a = 100 … 대각선화의 부정 a, ￢a ∈ 무한이진문자열, 그러나, a ↔ 자연수, ￢a ￢↔ 자연수. 무한이진수 ￢↔ 자연수. |자연수의 부분집합| > |자연수| 자연수 셀 수 있게(countable) 무한(많다) 자연수의 부분집합 셀 수 없이(uncountable) 무한(많다) 증명의 핵심 대각선화(diagonalization) 후에 부정한다. Russell에 영향을 준 것으로 예상. Self-recursion에 대한 부정. 내 개인 생각 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

Russell의 모순(paradox, 1901; 1911) Cantor의 naive set theory에 대한 부정 Let R = {x| x ￢∈ R} 매우 아름다운 집합에 대한 정의 집합도 집합의 원소가 될 수 있다. {{}, {{}}, {{{}}}, …} 집합이 그 집합 자신을 원소로 갖는 것은 이상하다. 사각형의 집합이 사각형의 집합을 원소로 가지지 않는다. 그러나, in x = R then (R ∈ R) ⇔ (R ￢∈ R). 자기자신으로 재귀(self-recursion)에 대한 부정. 자신을 부정하는 사람은 존재하지 않는다. x ￢∈ x . SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

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). SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

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). 큰일 났다! 그런데, 이거 모두 말장난(논리장난) 아닌가? 맞다() SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

서양 과학과 동양 인문학 서양 과학 동양 인문학 미래의 전산학 수학 또는 과학 F = ma. E = mc2. 19c말 – 20c초, 쉬운 과학과 공학을 이용한 무력으로 세계제패. 경제적 우월성 과학 또는 수학은 쉽다. 공학은 어렵다. 자연과 사람의 문제. Cantor, Russell, Gödel, Hilbert, ... 형식주의, 논리주의의 붕괴 과학(수학) 만능에 대한 수학자들의 경고. 동양 인문학 사람에 대한 이해와 존경 사람이 제일 어렵다. 미래의 전산학 사람의 문제를 다룬다. 기존의 공학과는 전혀 다른 새로운 학문이다. 프로그램학 SIGPL SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

전산학과 사람 미래학자들 좋은 프로그래밍언어 사람을 위한 프로그램학 전화기 망한다. 컴퓨터 망한다. 전 세계 인구의 1/3이 교환수 기계식 교환기, 컴퓨터 교환기 기술적 비약(Technical take-off) 컴퓨터 망한다. 전 세계 인구의 반이 프로그래머 ??? 새로운 파라다임. 좋은 프로그래밍언어 E. W. Dijkstra(1970년대) 사람을 위한 프로그래밍언어 vs. 기계를 위한 프로그래밍 언어 최광무(1990년대) 사람을 위한 프로그래밍언어 vs. 수학을 위한 프로그래밍 언어 사람을 위한 프로그램학 수학과의 만남 인문사회학과의 만남 사람과의 만남 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

미래에 지도자 수신제가(修身齊家) 치국평천하(治國平天下) 격물치지(格物致知) 성의정심(誠意正心) 미래에 지도자 공자, 대학 제 2장 격물치지(格物致知) 성의정심(誠意正心) 격물치지 이공학 공부 세상 무서운 줄 안다. 성의정심 인문사회학 공부 사람 귀한 줄 안다. 미래에 지도자 세상 무서운 줄 알고, 사람 귀한 줄 아는 사람 SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무

감사합니다 전산학과 인문사회학 공부 모두 열심히 하신 후에, 미래에 훌륭한 지도자가 되시기 바랍니다. SIGPL 겨울학교, 2012-02-03 한국과학기술원 전산학과 최광무