목차
머리말 = Ⅲ
제1장 계산 이론 = 11
1.1 오토마타 이론과 컴퓨터 관련 학문 = 12
1.2 수학적 배경 = 13
1.3 증명 방법 = 27
1.4 오토마타와 관련된 3가지 중요한 개념 = 30
1.5 문법 = 36
1.6 오토마타 = 41
1.7 오토마타의 응용 = 43
연습문제 및 생각할 점 = 46
제2장 유한 오토마타(Finite Automata) = 51
2.1 유한 오토마타 = 52
2.2 유한 상태 시스탬 = 57
2.3 DFA와 언어 = 61
2.4 정규언어 = 68
2.5 비결정적 유한 오토마타 = 71
2.6 비결정성의 필요성 = 74
2.7 NFA와 DFA의 동치성 = 76
2.8 NFA에서 DFA로의 변환 = 77
2.9 유한 오토마타의 최소화 = 85
2.10 출력이 있는 유한 오토마타 = 89
2.11 유한 오토마타의 응용 = 93
연습문제 및 생각할 점 = 97
제3장 정규 언어와 정규 문법 = 107
3.1 정규 표현 = 108
3.2 정규 표현과 언어 = 108
3.3 정규 표현과 오토마타 = 113
3.4 정규 문법 = 123
3.5 정규 문법과 유한 오토마타 = 125
연습문제 및 생각할 점 = 129
제4장 정규 언어의 성질 = 137
4.1 정규 언어의 특성 = 138
4.2 정규 집합의 닫힌 성질들 = 139
4.3 비정규 언어의 판별 = 145
4.4 정규 집합의 결정 알고리즘과 결정 문제 = 152
연습문제 및 생각할 점 = 155
제5장 문맥자유 언어와 문맥자유 문법 = 159
5.1 문맥자유 언어 = 160
5.2 문맥자유 문법 = 163
5.3 유도와 언어 = 167
5.4 유도 트리 = 173
5.5 파싱과 애매성 = 179
5.6 본질적으로 애매한 CFG = 185
5.7 문맥자유 문법과 프로그래밍의 언어 = 186
연습문제 및 생각할 점 = 193
제6장 문맥자유 문법의 변형과 정규 형태 = 201
6.1 문법의 변형 = 202
6.2 좌측순환의 제거 = 203
6.3 불필요한 심볼의 제거 = 205
6.4 λ- 생성규칙의 제거 = 210
6.5 단일 생성규칙의 제거 = 213
6.6 촘스키 정규형태 = 214
6.7 그레이바하 정규형태 = 217
연습문제 및 생각할점 = 221
제7장 푸쉬다운 오토마타 = 227
7.1 푸쉬다운 오토마타 = 228
7.2 비결정적 푸쉬다운 오토마타 = 230
7.3 푸쉬다운 오토마타와 CFL = 237
7.4 결정적 푸쉬다운 오토마타 = 239
연습문제 및 생각할 점 = 242
제8장 문맥자유 언어들의 성질 = 247
8.1 CFL에 대한 펌핑 정리 = 248
8.2 CFL에서의 닫힌 성질 = 253
8.3 CFL에서의 결정 알고리즘 = 257
8.4 멤버쉽의 결정 = 259
연습문제 및 생각할 점 = 262
제9장 튜링머신(Turing Machine) = 265
9.1 튜링머신의 배경 = 266
9.2 튜링머신 모델 = 267
9.3 언어를 인식하는 기능으로서의 튜링머신 = 275
9.4 계산이 가능한 언어들과 함수들 = 280
9.5 서브루틴을 이용한 튜링머신의 구성 = 286
9.6 변형된 튜링머신들 = 288
9.7 튜링의 논제 = 293
연습문제 및 생각할 점 = 295
제10장 선형한계 오토마타와 형식 언어의 포함 관계 = 299
10.1 선형한계 오토마타 = 300
10.2 문맥민감 문법과 CSL = 302
10.3 무제한 문법 = 304
10.4 촘스키 포함 관계 = 306
10.5 순환열거가능 언어와 순환적 언어 = 308
연습문제 및 생각할 점 = 310
제11장 결정불가능과 유니버셜 튜링 머신 = 313
11.1 결정가능과 결정불가능 = 314
11.2 튜링머신의 멈춤문제 = 314
11.3 유니버셜 튜링머신 = 318
11.4 포스트의 대응 문제 = 320
11.5 PCP의 응용 = 323
연습문제 및 생각할 점 = 326
부록 = 329
부록1. 유한 오토마타의 구현 예 = 330
부록2. 파스칼 언어의 BNF 정의 = 345
부록3. 용어 해설 = 351
참고 문헌 = 363
찾아보기 = 367
