Detail View

목차
1 계산이론 개요 = 1  
 1.1 수학적 개요 및 표기법 = 3
  집합 = 3
  함수와 관계 = 6
  그래프와 트리 = 8
  증명 기법 = 10
 1.2 세가지 기초 개념 = 17
  언어 = 17
  문법 = 21
  오토마타 = 27
 1.3 응용 = 31
2 유한 오토마타 = 39
 2.1 결정적 유한 인식기 = 39
  결정적 유한 인식기와 전이 그래프 = 40
  언어와 결정적 유한 인식기 = 42
  정규 언어 = 47
 2.2 비결정적 유한 인식기 = 52
  비결정적 인식기의 정의 = 52
  비결정성을 사용하는 이유 = 56
 2.3 결정적 유한 인식기와 비결정적 유한 인식기의 동치성 = 60
 2.4 유한 오토마타에서의 상태의 수 축소 = 67
3 정규 언어와 정규 문법 = 75
 3.1 정규 표현 = 75
  정규 표현의 정의 = 76
  정규 표현과 관련된 언어 = 76
 3.2 정규 표현과 정규 언어의 관계 = 82
  정규 표현에 대한 정규 언어 = 82
  정규 언어에 대한 정규 표현 = 84
  단순한 패턴을 묘사하기 위한 정규 표현 = 90
 3.3 정규 문법 = 93
  우선형 문법과 좌선형 문법 = 94
  우선형 문법의 정규 언어 생성 = 95
  정규 언어에 대한 우선형 문법 = 97
  정규 언어와 정규 문법간의 동치성 = 99
4 정규 언어의 성질 = 103
 4.1 정규 언어의 페로 성질 = 104
  간단한 집합 연산에 대한 페로 성질 = 104
  기타 연산에 대한 페포 성질 = 106
 4.2 정규 언어에 대한 기본적인 문제들 = 115
 4.3 비정규 언어의 식별 = 118
  피전홀 원리의 이용 = 119
  펌핑 보조정리 = 120
5 문맥-자유 언어 = 131
 5.1 문맥-자유 문법 = 132
  문맥-자유 언어의 예 = 133
  좌측우선 유도와 우측우선 유도 = 135
  문장형태와 유도 트리와의 관계 = 138
 5.2 파싱과 모호성 = 142
  파싱과 소속성 = 142
  문법과 언어에서의 모호성 = 147
 5.3 문맥-자유 문법과 프로그래밍 언어 = 152
6 문맥-자유 문법의 단순화와 정규형 = 155
 6.1 문법의 변형 방법 = 156
  유용한 치환 규칙 = 156
  쓸모없는 생성 규칙의 제거 = 158
  λ-생성 규칙의 제거 = 162
  단위-생성 규칙의 제거 = 164
 6.2 정규형 = 171
  Chomsky 정규형 = 171
  Greibach 정규형 = 174
 6.3 문맥-자유 문법에 대한 소속성 알고리즘 = 177
7 푸시다운 오토마타 = 181
 7.1 비결정적 푸시다운 오토마타 = 182
  푸시다운 오토마타의 정의 = 182
  푸시다운 오토마타에 의하여 인식되는 언어 = 186
 7.2 푸시다운 오토마타와 문맥-자유 언어 = 190
  문맥-자유 언어에 대한 푸시다운 오토마타 = 190
  푸시다운 오토마타에 대한 문맥-자유 언어 = 195
 7.3 결정적 푸시다운 오토마타와 결정적 문맥-자유 문법 = 201
 7.4 결정적 문맥-자유에 대한 문법 = 206
8 문맥-자유 언어의 성질 = 211
 8.1 두 펑핑 보조정리들 = 211
  문맥-자유 언어에 대한 펑핑 보조정리 = 212
  선형 언어에 대한 펑핑 보조정리 = 216
 8.2 문맥-자유 언어에 대한 페포 성질과 경정 알고리즘 = 220
  문맥-자유 언어들의 페포 = 220
  문맥-자유 언어들의 몇몇 결정 가능한 성질 = 224
9 튜링 기계 = 229
 9.1 표준 튜링 기계 = 230
  튜링 기계의 정의= 230 
  언어 승인기로서의 튜링 기계 = 236
  변환기로서의 튜링 기계 = 240
 9.2 복잡한 태스크를 위한 튜링 기계 결합 = 246
 9.3 튜링 명제 = 251
10 튜링 기계의 다른 모델 = 257
 10.1 튜링 기계의 주제에 대한 사소한 변화 = 258
  오토마타 부류들의 동치성 = 258
  스테이-옵션을 갖는 튜링 기계 = 259
  절반-무한 테이프를 갖는 튜링 기계 = 261
  오프-라인 튜링 기계 = 263
 10.2 복잡한 기억장치를 갖는 튜링 기계 = 266
  다중테이프 튜링 기계 = 266
  다차원 튜링 기계 = 268
 10.3 비결정적 튜링 기계 = 271
 10.4 범용 튜링 기계 = 274
 10.5 선형 한정 오토마타 = 279
11 형식 언어의 계층과 오토마타 = 283
 11.1 재귀적 언어와 재귀적으로 열거 가능한 언어 = 284
  재귀적으로 열거하지 않은 언어들 = 286
  재귀적으로 열거 가능하지 않은 언어 = 287
  재귀적으로 열거 가능하지만 재귀적이 안닌 언어 = 289
 11.2 무제한 문법 = 291
 11.3 문맥-인식 문법과 언어 = 297
  문맥-인식 언어와 선형 한정 오토마타 = 298
  재귀적 언어와 문맥-인식 언어들 사이의 관계 = 300
 11.4 Chomsky 계층 = 303
12 알고리즘적인 계산의 한계 = 306
 12.1 튜링 기계로 해결할 수 없는 문제들 = 308
  계산 가능성과 결정 가능성 = 308
  튜링 기계의 정지 문제 = 309
  결정 불가능한 문제를 다른 문제로 변형하기 = 313 
 12.2 재귀적으로 열거 가능한 언어에 대한 결정 불가능 문제 = 317
 12.3 Post 대응 문제 = 320
 12.4 문맥-자유 언어에 대한 결정 불가능 문제 = 327
 12.5 효율성에 대한 질문 = 330
13 다른 계산 모델 = 333
 13.1 재귀 함수 = 335
  원시 재귀 함수 = 336
  Ackermann 함수 = 339
  λ-재귀 함수 = 341
 13.2 Post 시스템 = 344
 13.3 재기록 시스템 = 348
  행렬 문법 = 348
  Markov 알고리즘 = 349
  L-시스템 = 350
14 계산 복잡도의 개관 = 353
 14.1 계산의 효율성 = 354
 14.2 튜링 기계 모델과 복잡도 = 356
 14.3 언어군과 복잡도 부류 = 359
 14.4 복잡도 부류 P와 NP = 363
 14.5 몇 가지 NP 문제들 = 365
 14.6 다항식 시간 축소 = 369
 14.7 NP 완전성과 미해결 문제 = 371
부록 A. 유한-상태 변환기 = 373
 A.1 일반적인 구조 = 375
 A.2 Mealy 기계 = 376
 A.3 Moore 기계 = 378
 A.4 Moore 기계와 Mealy 기계의 동치성 = 380
 A.5 Mealy 기계의 최소화 = 384
 A.6 Moore 기계의 최소화 = 388
 A.7 유한-상태 변환기의 한계 = 390
부록 B. JFLAP : 추천의 글 = 393
해답 = 395
참고문헌 = 441
찾아보기 = 443