오토마타 및 형식언어 - 무료예쁜표지계산모델, 김삼묘, 이한출판사 풀이 -

From : http://www.needreport.com/index.php?document_srl=327936
오토마타 및 형식언어 - 계산모델, 김삼묘, 이한출판사 풀이

자료 (압축파일).zip

오토마타 및 형식언어 - 계산모델, 김삼묘, 이한출판사

교과서의 제목과 같이 이 과목에서 우리는 전자계산 (또는 컴퓨터공학)에서 가장 기본적인 계산모델인 automata와 formal language를 배우게 됩니다. Formal language는 문법에 의하여 만들어진 (즉 정의된) 언어를 말하며, automata는 형식언어를 인식할 수 있는 개념적인 단순한 계산 장치입니다. 컴퓨터를 가지고 계산하는(compute) 문제를 이 과목에서는 automata가 형식언어를 인식하는(recognize) 문제로 단순화 하여 다루고 있습니다. Automata는 언어 인식을 위한 가장 기본적인 요소를 갖추고 있습니다. 언어의 복잡도, 즉 인식의 난이도에 따라, 이를 인식하는 automat의 능력도 달라지는데, 이 과목에서는 전통적으로 널리 알려져 있으며 자주 이용되는 네 종류의 automata와 이들이 인식하는 형식언어를 배우게 될 것입니다.우리는 주어진 문법이 정하는 (발생한다고도 함) 언어를 알아내고, 반대로 언어가 주어졌을 때, 이를 발생하는 문법을 만드는 기법도 배울 것이며, 제한적이지만, 주어진 언어를 인식하는 automaton을 설계하는 방법도 배울 것입니다. 이러한 지식을 바탕으로 우리는 형식언어와 이를 인식하는 automata 사이의 관계를 이해하게 될 것이며, 나아가 컴퓨터 시스템을 이해할 수 있는 안목(perspective)도 갖추게 됩니다. 이 책의 14 장에서 이를 뒷받침 하는 몇 가지 예를 볼 것입니다.컴퓨터 이론 과목을 위한 교과서는 일반적으로 책의 말미에 판별불능성(undecidability), 해결불능성(unsolvability), 또는 계산불능성 (uncomputability), 등의 제목 하에 계산으로 답을 얻을 수 없는 문제들을 소개하고 이를 증명해 보입니다. 이 교재는 2년 또는 3년차 컴퓨터 전공학생이 한 학기 동안에 배우기 위하여 만들어진 것으로 위와 같은 내용을 다룰 수 있는 충분한 시간이 없으므로 본 교재에 포함하지 않기로 하였습니다.

Chapter 01 준비(Preliminaries)

1.1 표기관례(Notational Convention) 14

1.2 증명법(Proof Techniques) 17

연습문제 29

Chapter 02 형식언어(Formal Languages)

2.1 Rule에 의한 언어 생성 37

2.2 Definition : Formal Languages and Grammars 42

2.3 문법과 언어 예 44

연습문제 48

Chapter 03 기타 Language 표현 Models

3.1 L-systems 52

3.2 Syntax Flow Graph 55

3.3 Regular Expression 57

연습문제 60

Chapter 04 Automata

4.1 Deterministic Turing Machines(결정성 투어링 장치) 65

4.3 Deterministic Linear Bounded Automata(DLBA) 72

4.4 Deterministic Pushdown Automata(DPDA) 73

4.5 Deterministic Finite Automata(DFA) 78

연습문제 84

Chapter 05 비결정성 오토마타(Nondeterministic Automata)

5.1 Nondeterministic Finite Automata(NFA) 91

5.2 Nondeterministic Pushdows Automata(NPDA) 95

5.3 Nondeterministic Turing Machines(NTM) 및 Nondeterministic Linear Bounded Automata(NLBA) 98

5.4 Nondeterministic Algorithms 99

5.5 NFA와 e-transitions 102

5.6 FA의 e-transitions 제거하기 103

연습문제 107

Chapter 06 여러 형태의 Automata

6.1 Transducers : 출력이 있는 Automata 110

6.2 여러 형태의 TM 111

6.3 여러 형태의 PDA 113

6.4 여러 형태의 FA 118

6.5 Churchs Hypothesis 121

연습문제 122

Chapter 07 언어 및 오토마타 체계 Ⅰ

7.1 Chomsky Hierarchy 128

7.2 Characterization(특성화 관계) 증명 130

연습문제 144

Chapter 08 FA 다듬기

8.1 NFA를 DFA로 전환하기 147

8.2 DFA를 최소화 하기 149

연습문제 156

Chapter 09 형식언어의 특성(Properties of the Formal Languages)

9.1 Regular Language의 특성 158

9.2 Context-free Language의 특성 162

연습문제 165

Chapter 10 CFG 다듬기

10.1 e-production Rule 수를 줄이기 168

10.2 Unit production Rule 줄이기 172

10.3 CFG의 불필요한 Symbol 제거하기 174

10.4 CFG의 Normal Form(표준형식) 180

연습문제 185

Chapter 11 CFG의 Ambiguity(모호성)

11.1 Parse Tree 188

11.2 Parse Tree와 Ambiguity 190

11.3 CFG의 모호성 제거하기 191

연습문제 196

Chapter 12 Chomsky Hierarchy Ⅱ(정규포함 관계)

12.1 포함관계 201

12.2 Pumping Lemma 203

12.3 Pumping Lemma 응용 208

12.4 CFL에 대한 Pumping Lemma 213

12.5 CFL에 대한 Pumping Lemma : 응용 214

12.6 Ogdens Lemma 218

12.7 CFL에 대한 Pumping Lemma : 증명 220

연습문제 223

Chapter 13 Parsing

13.1 Derivation 227

13.2 LL(k) Parsing 전략 229

13.3 LL(k) Parser 만들기 234

13.4 LR(k) Parsing 241

13.5 LR(k) Grammar(정의) 252

연습문제 255

Chapter 14 Formal Language 응용

14.1 Hyper Text Markup Language(HTML) 258

14.2 DTD와 259

14.3 Gene Grammar(유전자 문법) 264

14.4 Lex and YACC 269

Chapter 15 형식언어 및 오토마타 체계 Ⅲ

15.1 TM이 인식할 수 없는 언어 275

15.2 Universal TM 281

15.3 Enumerble Languages 282

15.4 Recursive Language 287

15.5 Characterization 증명 294

연습문제 314

Appendix

A : Pascal Syntax Flow Graph 316

B : 2-way FA 언어를 인식하는 1-way FA 만들기 322

C : FA를 가지고 Regular Expression 구하기(dynamic programming 기법) 330

D : DCFL의 특성 336

E : Pumping Lemma를 만족하는 Non-regular Language 352

F : CYK Algorithm 354

자료 (압축파일).zip