목차
제1장 예비지식
1.1 스트링, 알파벳 그리고 언어 = 3
1.2 그래프와 트리 = 4
1.3 귀납적 증명(Inductive Proof) = 7
1.4 집합 기호 = 8
1.5 관계(Relations) = 11
1.6 이 교재의 개요 = 13
연습문제 = 16
제2장 유한 오토마타와 정규식
2.1 유한 상태 시스템 = 21
2.2 기본 정의 = 24
2.3 비결정 유한 오토마타 = 28
2.4 ε - 이동으로서 유한 오토마타 = 35
2.5 정규식 = 41
2.6 양방향 유한 오토마타 = 52
2.7 출력을 지닌 유한 오토마타 = 62
2.8 유한 오토마타의 응용 = 66
연습문제 = 68
제3장 정규집합의 성질
3.1 정규집합에 대한 펌핑 정의 = 79
3.2 정규집합의 폐쇄 성질 = 83
3.3 정규집합에 대한 결정 알고리즘 = 91
3.4 Myhill - Nerode 정리와 유한 오토마타의 최소화 = 93
연습문제 = 103
제4장 문맥-자유 문법
4.1 동기와 개요 = 111
4.2 문맥-자유 문법 = 113
4.3 파생트리(Derivation Trees) = 117
4.4 문맥-자유 문법의 간단성 = 125
4.5 Chomsky Normal 형식 = 132
4.6 Greibach Normal 형식 = 135
4.7 고질적인 애매모호한 문맥-자유 언어의 존재 = 142
연습문제 = 149
제5장 Pushdown 오토마타
5.1 비공식적 표현 = 155
5.2 정의 = 157
5.3 Pushdown = 163
연습문제 = 174
제6장 문맥-자유 언어의 성질
6.1 CFL들에 대한 펌핑 정의 = 179
6.2 CFL의 폐쇄 성질 = 186
6.3 CFL에 대한 결정 알고리즘 = 196
연습문제 = 203
제7장 Turing 기계
7.1 개념 = 209
7.2 Turing 기계 모델 = 210
7.3 계산할 수 있는 언어와 함수 = 214
7.4 Turning 기계 구성에 의한 기법 = 217
7.5 Turning 기계의 변경 = 226
7.6 Church의 가설 = 235
7.7 계수로서 Turning 기계 = 237
7.8 기본 모델에 대해 동등하게 제한된 Turning 기계 = 241
연습문제 = 247
제8장 미정의(undecidability)
8.1 문제 = 251
8.2 순환과 순환적으로 나열 가능한 언어의 성질 = 253
8.3 전체 Turing 기계와 비결정 문제 = 256
8.4 Rice 정의와 몇 가지 더 결정할 수 없는 문제들 = 262
8.5 Post의 대응 문제의 비결정성 = 274
8.6 TM의 확실하고 불확실한 계산:CFL 문제들이 비결정성임을 증명하는 도구 = 284
8.7 Greibach 이론 = 290
8.8 순환적 함수 이론에 대한 개념 = 293
8.9 Oracle 계산 = 297
연습문제 = 303
제9장 Chomsky 계층구조
9.1 정규문법(Regular Grammars) = 309
9.2 제한이 없는 문법 = 313
9.3 문맥 의존형 언어 = 318
9.4 언어들의 계층들 사이의 관계 = 322
연습문제 = 326
제10장 결정적 문맥-자유 언어
10.1 DPDA것에 대한 정규 형식 = 332
10.2 보수하에 DCFL의 폐쇄 = 334
10.3 기계를 예측(Predicting Machines) = 341
10.4 DCFL의 부가적 폐쇄 성질 = 346
10.5 DCFL의 결정 성질 = 351
10.6 LR(0) 문법 = 353
10.7 LR(0) 문법과 DPDA = 361
10.8 LR(k) 문법 = 371
연습문제 = 377
제11장 언어 계보의 폐쇄 성질
11.1 트리오 완전트리오(Trios and Full Trios) = 381
11.2 순차적 기계 매핑을 일반화 = 383
11.3 트리오의 다른 폐쇄 성질 = 390
11.4 언어의 추상적 계보(Abstract Families of Languages) = 392
11.5 AFL 연산의 독립성 = 393
11.6 요약 = 394
연습문제 = 397
제12장 다른 중요한 언어 계층의 현저한 특징
12.1 시간과 공간 복잡도 정의 = 403
12.2 보조적인 Pushdown 오토마타 = 407
12.3 스택 오토마타 = 413
12.4 인덱스된 언어(Indexed Languages) = 424
12.5 개발적 시스템 = 426
12.6 요약 = 429
연습문제 = 430
찾아보기 = 433
