목차
0. 수학기초
0.1 기초논리 = 1
0.2 집합개념 = 9
0.3 집합연산 = 11
0.4 관계와 함수 = 15
0.5 귀납법(INDUCTION) = 23
1. 알파벳과 언어
1.1 알파벳, 단어, 언어 = 27
1.2 스트링의 연산 = 30
1.3 언어의 연산 = 33
(연습문제) = 43
2. 정규 언어
2.1 알파벳 상의 언어 = 47
2.2 정규 언어와 정규식 = 51
2.3 결정적 유한 오토마타 = 57
2.4 dfa와 언어 = 64
2.5 비결정적 유한 오토마타 = 66
2.6 nfa와 dfa의 동일성 = 73
2.7 -전이 = 78
2.8 유한 오토마타와 정규식 = 83
2.9 정규 언어의 특성 = 93
2.10 정규식과 유한 오토마타의 응용 = 101
(연습문제) = 103
3. 문맥 자유 언어
3.1 정규 문법 = 117
3.2 정규 문법과 정규 언어 = 122
3.3 문맥 자유 문법 = 128
3.4 유도 과정 또는 파스트리와 모호성 = 131
3.5 문맥 자유 문법의 단순화 = 136
3.6 문맥 자유 언어의 속성 = 150
3.7 푸쉬다운 오토마타 = 160
3.8 푸쉬다운 오토마타와 문맥 자유 언어 = 169
3.9 그라이바하 정규 형식 = 181
(연습문제) = 188
4. 튜링머신
4.1 기본 정의 = 193
4.2 언어 인식기로서의 튜링머신 = 200
4.3 튜링머신 구성 KIT = 208
4.4 튜링머신의 수정 = 220
4.5 유니버설 튜링머신 = 232
5. 튜링머신과 언어
5.1 튜링머신에 의해 인식되는 언어 = 235
5.2 정규, 문맥, 자유, 순환적, 그리고 순환적 열거 가능 언어들 = 237
5.3 순환적과 순환적 열거 가능 언어 = 243
5.4 무제약(unrestricted) 언어와 순환적 열거 가능 언어 = 250
5.5 문맥 민감(context-sensitive)언어와 Chomsky 계층 = 259
6. 결정가능성
6.1 정지문제(halting problem) = 269
6.2 포스트 대응문제 = 273
6.3 결정불가능과 문맥자유 언어 = 291
(연습문제) = 297
7. 계산적인 복잡도(Computational Complexity)
7.1 공간 복잡도 = 299
7.2 시간 복잡도 = 307
7.3 복잡도 이론 개론 = 327
(연습문제) = 327
참고문헌 = 331
찾아보기 = 333
