목차 일부
제1장 예비사항
1.1 스트링, 알파베트 및 언어 ... 1
1.2 그래프와 트리 ... 3
1.3 귀납적 증명 ... 6
1.4 집합 표시법 ... 7
1.5 관계 ... 9
1.6 이 책의 개요 ... 12
연습문제 ... 15
연습문제해답 ... 18
제2장 유한 오토마타(finite automate)와 정규...
더보기
목차 전체
제1장 예비사항
1.1 스트링, 알파베트 및 언어 ... 1
1.2 그래프와 트리 ... 3
1.3 귀납적 증명 ... 6
1.4 집합 표시법 ... 7
1.5 관계 ... 9
1.6 이 책의 개요 ... 12
연습문제 ... 15
연습문제해답 ... 18
제2장 유한 오토마타(finite automate)와 정규표현(regular expression)
2.1 유한 상태 시스템(finite state system) ... 21
2.2 기본 정의 ... 25
2.3 비결정적인 유한 오토마타(nondeterministic finite automata : NFA) ... 30
2.4 e-동작이 있는 유한 오토마타 ... 37
2.5 정규 표현(regular expression) ... 43
2.6 양방향 유한 오토마타(two-way finite automata) ... 54
2.7 출력이 있는 유한 오토마타 ... 64
2.8 유한 오토마타의 응용 ... 69
연습문제 ... 71
연습문제해답 ... 80
제3장 정규집합의 성질들
3.1 정규 집합에 관한 pumping lemma ... 86
3.2 정규 집합의 닫힌 성질들 ... 90
3.3 정규 집합에 대한 결정 알고리즘들 ... 98
3.4 Myhill-Nerode 정리와 유한 오토마타의 최소화 ... 101
연습문제 ... 112
연습문제해답 ... 117
제4장 문맥 자유 문법(context-free grammar : CFG)
4.1 동기와 머릿말 ... 121
4.2 문맥 자유 문법(context-free grammar : CFG) ... 124
4.3 유도 트리(derivation tree) ... 128
4.4 문맥 자유 문법의 단순화 ... 137
4.5 Chomsky 정규 형태(Chomsky normal form : CNF) ... 145
4.6 Greibach 정규 형태(Greibach normal form : GNF) ... 147
4.7 본질적으로 애매한 문맥 자유 문법의 존재 ... 155
연습문제 ... 161
연습문제해답 ... 165
제5장 Pushdown Automata
5.1 비공식적인 설명 ... 167
5.2 정의 ... 170
5.3 Pushdown automata와 문맥 자유언어 ... 177
연습문제 ... 187
연습문제해답 ... 190
제6장 문맥자유언어(context-free language : CFL)의 특징들
6.1 CFL에 대한 pumping lemma ... 195
6.1 CFL의 닫힌 성질들 ... 203
6.3 CFL에 대한 결정 알고리즘 ... 213
연습문제 ... 220
연습문제해답 ... 224
제7장 turing 기계
7.1 서론 ... 227
7.2 Turing 기계 모형 ... 229
7.3 계산할 수 있는 언어들과 함수들 ... 234
7.4 Turing 기계 구성에 대한 기법 ... 238
7.5 Turing 기계의 수정 ... 248
7.6 Church의 가설 ... 259
7.7 열거기(enumerator)로서의 Turing기계 ... 261
7.8 기본 모형과 동등한 제한된 Turing기계 ... 267
연습문제 ... 273
제8장 결정할 수 없음(undecidability)
8.1 문제 ... 278
8.2 순환적인 언어(recursive language)와 순환적으로 열거할 수 있는 언어(recursively enuerable language)들의 성질들 ... 281
8.3 보편적인 Turing기계(universal Turing machine)와 결정할 수 없는 문제들 ... 284
8.4 Rice의 정리와 또 다른 결정할 수 없는 문제들 ... 291
8.5 Post대응 문제(Post Correspondence Problem : PCP)의 결정할 수 없는 성질 ... 305
8.6 TM의 유효하고 유효하지 않은 계산들 : CFL문제들이 결정할 수 없음을 증명하는데 대한 수단 ... 316
8.7 Greibach의 정리 ... 323
8.8 순환적 함수(recursive function) 이론의 소개 ... 327
8.9 Oracle 계산 ... 331
연습문제 ... 338
연습문제해답 ... 341
제9장 Chomsky 분류 체계
9.1 정규 문법(regular grammar) ... 345
9.2 제한이 없는 문법(unrestricted grammar) ... 350
9.3 문맥 민감 언어들(context sensitive languages) ... 356
9.4 언어들 집단사이의 관계 ... 361
연습문제 ... 364
연습문제해답 ... 367
제10장 결정적인 문맥 자유 언어들(deterministic context-free languages)
10.1 DPDA의 정상 형태 ... 372
10.2 여집합에서 DCFL의 닫힌 성질 ... 375
10.3 예측 기계(predicting mechine) ... 382
10.4 DCFL의 또 다른 닫힌 성질들 ... 387
10.5 DCFL의 닫힌 성질들 ... 392
10.6 LR(o) 문법 ... 395
10.7 LR(o) 문법과 DPDA ... 403
10.8 LR(k) 문법 ... 416
연습문제 ... 422
연습문제해답 ... 424
제11장 언어들의 집단의 닫힌 성질들
11.1 트리오(trio)와 꽉 찬 트리오(full trio) ... 429
11.2 일반화된 순차적인 기계의 사상(mapping) ... 432
11.3 트리오(trio)의 다른 닫힌 성질들 ... 439
11.4 언어들의 추상적인 집단 ... 441
11.5 AFL연산들의 독립성 ... 443
11.6 요약 ... 444
연습문제 ... 447
연습문제해답 ... 449
제12장 계산적인 복잡도 이론
12.1 정의 ... 454
12.2 1차 함수적인 속력 증가(linear speed-up), 테이프 압축(tapecompression)및 테이프 갯수의 축소 ... 458
12.3 분류 체계 정리(hierarchy theorem) ... 470
12.4 복잡도 측정들 사이의 관계 ... 479
12.5 번역 보조 정리(translation lemma)와 비결정적인 분류체계(nondeterministic hierarchy) ... 483
12.6 일반적인 복잡도 측정의 특성들 : 간격(gap), 속력증가(speedup) 그리고 합집합 정리 ... 489
12.7 공리적인 복잡도 이론 ... 500
연습문제 ... 504
연습문제해답 ... 511
제13장 어려운 문제들 (intractable problems)
13.1 다항식인 시간과 공간 ... 516
13.2 몇가지 NP-complete 문제들 ... 522
13.3 co-NP 집합 ... 551
13.4 PSPACE-compete 문제들 ... 554
13.5 P와 NSPACE(LOG n)에 대하여 complete한 문제들 ... 561
13.6 풀기 어렵다고(intractable) 입증된 몇몇 문제들 ... 566
13.7 oracle이 있는 Turing기계에 대한 P＝NP의 질문 : P＝NP 여부를 이야기 할수 있는 능력의 한계 ... 585
연습문제 ... 591
연습문제해답 ... 603
제14장 다른 중요한 언어 집단들의 특징들
14.1 보조 pushdown 오토마타(auxiliary pushdown automata : APDA) ... 610
14.2 스택 오토마타(stack automata) ... 616
14.3 지수화된 언어들(indexed languages) ... 630
14.4 발전 시스템 ... 632
14.5 요약 ... 635
연습문제 ... 636
연습문제해답 ... 637
BLIOGRAPHY ... 639
찾아보기 ... 655
더보기 닫기
Export to Refworks
캠퍼스간대출
소재불명도서
자료배달서비스
인쇄
