제 11장. 형식언어와 오토메타의 Hierarchy 학습목표 TM과 연관된 형식언어/문법에 대해 알아보고 언어 사이의 포함관계를 총정리 해본다 개념적인 내용의 비중이 커집니다. 세부사항 보다도 전체적인 관계와 흐름에 주의를 기울입시다.

cf) valid only for L-{λ} 개요 CFL에서와 마찬가지로 편의상 Empty string이 없는 언어를 가정 합니다 cf) valid only for L-{λ} Recursive and Recursively Enumerable Languages Unrestricted Grammars Context-Sensitive Grammars and Languages The Chomsky Hierarchy TM이 accept하는 언어와 그 언어를 생성하는 문법 Linear Bounded Automata와 연관된 문법과 언어

Recursive Recursively Enumerable Languages Def 1 Def 2  비슷해 보이지만 그 차이를 명확히 이해할 것

Enumeration Procedure enumeration procedure for recursive language L r.e language를 위해서는 열거하는 방법에 좀 신경을 써야… 순서 다르게 p. 277 처럼 M이 생성된 스트링을 한 스텝씩만 처리  Halt하지 않는 스트링 때문에 진전되지 않는 문제해결 결론: enumeration procedure가 존재하는 언어는 recursively enumerable

① Recursively enumerable 하지 않은 언어의 존재여부 실제 보이기 어려운 개념적인 언어이므로 수학의 힘을 빌려 개념적으로 이해합니다 실제 예들 ① Recursively enumerable 하지 않은 언어의 존재여부 Thm S : infinite countable set → 2 s : not countable pf) t1 1 t2 1 t3 0 . diagonalization (fewer TM than lang.  r.e.하지 않은 언어가 존재) Thm for Σ . ∃ lang. not r. e. ② Recursive enumerable 하지 않은 언어의 예 Thm ∃ a r.e. L whose complement is not r.e. ③ Recursive 이지만 recursively enumerable 하지는 않은 언어도 존재함

Homework : Exercises 11.1 7 : 답은 Yes이고, 6번의 해답을 이용해볼 것. 10 : 이것도 답은 Yes인데… nondeterminism을 이해하면 쉽게 해결가능.

Unrestricted Grammars Recursively Enumerable언어를 생성하는 문법 Def 아무런 제약이 없는 문법 Thm 11.6 (→) systematic enumeration S ⇒ w S ⇒ x⇒ w Unrestricted Grammar로부터 한 스텝에 얻어지는 스트링, 두 스텝에 얻어지는 스트링, … 결국 체계적으로 enumeration 할 수 있으므로 r.e. 언어 생성 가능

Unrestricted Grammars : 증명(1) 역으로 r.e. 언어를 생성하는 문법이 unrestricted grammar임을 보입시다 Unrestricted Grammars : 증명(1) Thm 11.6-1 (←) T.M. by U.G. produce G L(G) = L(M) TM의 작동을 UG로 흉내내기 ? 2 copies of w by Vab & Vaib ∀ a, b, i 시작부터 w를 두개 갖고 acceptance를 따진다!  변수로 표현 ① S → V□□S | SV□□ | T T → TVaa | Va0a ∀ a ∈ Σ  일단 q0w를 만든다. ② VaicVpq → VadVpjq for δ(qi, c)=(qj, d, R) VpqVaic → VpjqVad for δ(qi, c)=(qj, d, L)  V의 처음 indices는 copy해둔 w임을 이해할 것.

Unrestricted Grammars : 증명(2) ③ Vajb → a cVab → ca Vabc → ac □ → λ Accept를 확인하면 복사해둔 w를 출력하기 위해 변수의 처음 index를 출력한다. 예) ①번 규칙을 사용하여 초기 스트링 q0aa□를 생성 ②번 규칙을 사용하여 TM을 흉내내고 ③번 규칙으로 원래 w를 출력  변수들의 첫 index는 초기 w를 기억!

Unrestricted Grammars : 총정리  Unrestricted grammar로 생성되는 언어는 recursively enumerable언어!

Homework : Exercises 11.2 1 : 답도 있고 하니 잘~ 풀어볼 것. 6 : 좀 tedious한 맛은 있지만, 이 절에서 배운 constructive한 메커니즘을 제대로 이해하기 위해서 한번 풀어볼 것.

Context-Sensitive G & L UG와 CFG 사이의 다양한 문법 중에서 LBA와 연관된 문법에 대해 검토 properties noncontracting why context-sensitive ? xAy → xvy A의 좌우에 x와 y가 있을때 A를 v로 규칙적용

CSL and Linear Bounded Automata  CFL는 CSL의 proper subset 이구나!

CSL and LBA : 증명 pf. Show that derivations in CSG can be simulated by LBA two tracks : input string w + sentential forms derived using G possible sentential form | w | LBA is nondeterministic  올바른 production을 늘 guess할 수 있다 Thm 11.6의 과정을 초기 w의 길이만큼만 사용해서 할 수 있다 LBA로 할 수 있다!

Recursive 언어와 CSL의 관계 pf. CSG : noncontracting → ∃membership algorithm check all derivations of length up-to |w|m(|w|)  LBA가 TM보다 덜 강력하다!

Homework : Exercises 11.3 일반적으로 CF가 아닌 언어의 CSG를 구하는 것은 매우 어려운 문제 이기 때문에 대부분의 문제를 쉽게 해결할 수는 없다. 그 중에서 가장 쉬운 1 (a)와 1 (b)를 한번 시도해 볼 것.

Chomsky Hierarchy 다양한 형식언어의 포함관계 이해 LRE (Type 0) LCS (Type 1) LCF (Type 2) LREG (Type 3) LREC LDCF LCF LLIN LDCF LREG TM이 할 수 있는 능력에 대해서 알아보았는데, 다음 주에는 마지막으로 TM이 할 수 없는 일은 무엇인지 살펴보고, 계산이론으로의 도입을 시도합니다.