머리말 ... ⅲ
제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