상세정보

이 책은 계산 이론 입문 과목에 필수적인 내용들을 탁월하게 소개하였다. 이 제 3 개정판은 복잡한 개념들을 쉽게 설명하였고 견고한 수학적인 기반을 마련하였다고 칭찬을 받았었다. 저자는 학생들이 근본적인 원리에 집중하고 이해할 수 있도록 증명들에 대한 직관적인 동기를 제시하였고, 지나친 수학적인 세부 사항들은 피했다.

다수의 신중하게 선택된 예제들이 여러 곳에서 반복해서 주어졌다. 이러한 예제들은 학생들로 하여금 비교 학습을 통하여 이해를 확립하게 한다.
강사 지침서는 연습문제들에 대한 해를 요약하였고 그들의 교육적인 가치를 제안하였다. 연습문제들은 이론적인 혹은 실질적인 응용에 대한 강조와 함께 교과 내용을 뒷바침할 것이다.

정보제공 :

목차

머리말 = ⅲ

제1장 계산 이론 개요

 1.1 수학적 개요 및 표기법 = 3

 1.2 세 가지 기초 개념 = 16

 1.3 응용 = 31

제2장 유한 오토마타

 2.1 결정적 유한 인식기 = 39

 2.2 비결정적 유한 인식기 = 52

 2.3 결정적 유한 인식기와 비결정적 유한 인식기의 동치성 = 60

 2.4 유한 오토마타에서의 상태의 수 축소 = 67

제3장 정규 언어와 정규 문법

 3.1 정규 표현 = 75

 3.2 정규 표현과 정규 언어의 관계 = 82

 3.3 정규 문법 = 93

제4장 정규 언어의 특성

 4.1 정규 언어의 폐포 성질 = 106

 4.2 정규 언어에 대한 기본적인 문제들 = 118

 4.3 비정규 언어의 식별 = 121

제5장 문맥 - 자유 언어

 5.1 문맥 - 자유 문법 = 134

 5.2 파싱과 모호성 = 145

 5.3 문맥 - 자유 문법과 프로그래밍 언어 = 156

제6장 문맥 - 자유 문법의 단순화와 정규형

 6.1 문법을 변형하는 방법 = 160

 6.2 정규형 = 175

 6.3 문맥 - 자유 문법에 대한 소속성 알고리즘 = 182

제7장 푸시다운 오토마타

 7.1 비결정적 푸시다운 오토마타 = 186

 7.2 푸시다운 오토마타와 문맥 - 자유 언어 = 194

 7.3 결정적 푸시다운 오토마타와 결정적 문맥 - 자유 언어 = 205

 7.4 결정적 문맥 - 자유 언어에 대한 문법 = 210

제8장 문맥 - 자유 언어의 성질들

 8.1 두 펌핑 보조정리들 = 215

 8.2 문맥 - 자유 언어에 대한 폐포 성질과 결정 알고리즘 = 224

제9장 튜링 기계

 9.1 표준 튜링 기계 = 234

 9.2 복잡한 태스크를 위한 튜링 기계 결합 = 251

 9.3 튜링 명제 = 256

제10장 튜링 기계의 다른 모델들

 10.1 튜링 기계의 주제에 대한 사소한 변화 = 262

 10.2 복잡한 기억장치를 갖는 튜링 기계 = 270

 10.3 비결정적 튜링 기계 = 276

 10.4 범용 튜링 기계 = 279

 10.5 선형 한정 오토마타 = 284

제11장 형식 언어 계층과 오토마타

 11.1 순환적 언어와 순환적으로 열거가능한 언어 = 290

 11.2 무제한 문법 = 297

 11.3 문맥 - 인식 문법과 언어 = 304

 11.4 Chomsky 계층 = 310

제12장 알고리즘적인 계산의 한계

 12.1 튜링 기계에 의하여 해결할 수 없는 문제들 = 314

 12.2 순환적으로 열거 가능한 언어에 대한 결정불가능 문제 = 324

 12.3 Post 대응 문제 = 328

 12.4 문맥 - 자유 언어에 대한 결정불가능 문제 = 335

제13장 다른 계산 모델

 13.1 순환 함수들 = 341

 13.2 Post 시스템 = 350

 13.3 재기록 시스템 = 354

제14장 계산 복잡도 입문

 14.1 계산의 효율성 = 362

 14.2 튜링 기계와 복잡도 = 364

 14.3 언어군들과 복잡도 부류들 = 368

 14.4 복잡도 부류 P와 NP = 372

해답과 힌트 = 377

참고문헌 = 427

찾아보기 = 429