목차
수정판을 내며 = ⅴ
머리말 = ⅶ
제1장 간추림 = 1
1.1 모임 = 1
모임 = 1
모임의 연산 = 3
1.2 유향그래프 = 7
유향그래프 = 7
나무 = 8
1.3 함수와 관계 = 10
함수 = 10
관계 = 12
기수 = 17
1.4 증명 방법의 두 가지 보기 = 19
수학적 귀납법 = 19
대각논법 = 21
1.5 글자모임, 낱말과 언어 = 23
낱말과 표기 = 24
낱말과 언어의 연산법 = 26
∑*와 2∑*의 기수 = 28
연습문제 = 31
제2장 유한자동장치 = 35
2.1 유한자동장치 = 37
확정유한자동장치 = 37
dfa가 받아들이는 언어 = 41
구별되는 낱말 = 44
2.2 불확정유한자동장치 = 46
불확정유한자동장치 = 47
불확정유한자동장치가 받아들이는 언어 = 49
2.3 dfa와 nfa = 53
dfa와 동등한 nfa = 53
nfa와 동등한 dfa 만들기 = 55
-nfa = 59
2.4 dfa의 최소화 = 63
연습문제 = 68
제3장 정칙표시 = 71
3.1 정칙표시와 언어 = 72
정칙표시의 정의와 기호 = 72
유한한 언어 = 75
3.2 정칙표시와 유한자동장치 = 76
정칙표시에서 -nfa로 = 77
dfa에서 정칙표시로 = 82
연습문제 = 86
제4장 정칙언어의 특성 = 89
4.1 정칙언어와 비정칙언어 = 89
펌핑레마 = 90
Myhill-Nerode의 정리 = 93
4.2 정칙언어의 연산과 확정유한자동장치 = 97
정칙언어의 연산결과 = 97
연산결과의 정칙언어를 받아들이는 확정유한자동장치 = 99
4.3 정칙언어에 관한 결정문제 = 101
연습문제 = 104
제5장 문맥무관 문법 = 107
5.1 문맥무관 문법 = 107
정의와 기호 = 108
문맥무관언어 = 111
정칙언어와 정칙문법 = 115
5.2 유도나무 = 118
유도나무와 유도수열 = 118
모호성 = 124
5.3 축소된 문법과 표준형 = 127
쓸모없는 글자 = 127
빈 산출 = 133
한글자 산출 = 136
Chomsky 표준형 = 138
연습문제 = 141
제6장 내려누름자동장치 = 145
6.1 불확정내려누름자동장치 = 145
내려누름자동장치의 정의 = 146
내려누름자동장치가 받아들이는 언어 = 150
확정 내려누름자동장치 = 155
6.2 내려누름자동장치와 문맥무관언어 = 159
연습문제 = 166
제7장 문맥무관언어의 특성 = 169
7.1 펌핑레마 = 169
7.2 문맥무관언어의 연산 결과 = 174
7.3 문맥무관언어에 관한 결정문제 = 178
연습문제 = 181
제8장 Turing 계산기 = 183
8.1 계산의 모형 = 183
Turing 계산기 = 184
언어를 받아들이는 Tm = 188
함수를 계산하는 Tm = 192
8.2 Turing 계산기의 여러 변형 = 193
8.3 순환열거언어와 순환언어 = 202
8.4 언어열거하기 = 206
연습문제 = 210
제9장 무제약문법 = 213
9.1 무제약문법 = 213
9.2 무제약문법과 Turing 계산기 = 216
연습문제 = 220
제10장 풀 수 없는 결정문제들 = 223
10.1 온 Turing 계산기 = 224
10.2 멈춤 문제 = 228
10.3 Post의 대응문제 = 234
10.4 풀 수 없는 문맥무관언어에 관한 문제들 = 240
연습문제 = 242
참고문헌 = 245
