목차 일부
머리말
Chapter 01 준비
1.1 표기 관례(Notational Convention) ... 14
1.2 증명법(Proof Techniques) ... 16
Chapter 02 형식언어
2.1 Rule에 의한 언어 생성 ... 31
2.2 Definition : Formal Languages and Grammars ... 35
...
더보기
목차 전체
머리말
Chapter 01 준비
1.1 표기 관례(Notational Convention) ... 14
1.2 증명법(Proof Techniques) ... 16
Chapter 02 형식언어
2.1 Rule에 의한 언어 생성 ... 31
2.2 Definition : Formal Languages and Grammars ... 35
2.3 문법과 언어 예 ... 37
Chapter 03 기타 Language 표현 Models
3.1 L-systems ... 42
3.2 Syntax Flow Graph ... 45
3.3 Regular Expression ... 47
Chapter 04 Automata
4.1 Deterministic Turing Machines(결정성 투어링 장치) ... 53
4.2 Deterministic linear bounded automata(DLBA) ... 60
4.3 Deterministic pushdown automata(DPDA) ... 61
4.4 Deterministic finite automata(DFA) ... 66
Chapter 05 비결정성 오토마타(Nondeterministic Automata)
5.1 Nondeterministic Finite Automata(NFA) ... 73
5.2 Nondeterministic Pushdown Automata(NPDA) ... 77
5.3 Nondeterministic Turing Machines(NTM) and Nondeterministic Linear Bounded Automata(NLBA) ... 79
5.4 Nondeterministic Algorithms ... 81
5.5 NFA와 ε-transitions ... 83
5.6 FA의 ε-transitions 제거하기 ... 84
Chapter 06 여러 형태의 Automata
6.1 Transducers : 출력이 있는 Automata ... 90
6.2 여러 형태의 TM ... 91
6.3 여러 형태의 PDA ... 93
6.4 여러 형태의 FA ... 96
6.5 Church's Hypothesis ... 100
Chapter 07 형식 언어 및 오토마타 체계 Ⅰ(Chomsky Hierarchy Ⅰ)
7.1 Chomsky Hierarchy 포함관계 ... 105
7.2 Characterization(특성화 관계) ... 106
Chapter 08 FA 다듬기
8.1 NFA를 DFA로 전환하기 ... 119
8.2 DFA를 최소화 하기 ... 121
Chapter 09 형식언어의 특성(Properties of the Fomal Languages)
9.1 Regular language의 특성 ... 126
9.2 Context-free Language 들의 특성 ... 130
Chapter 10 CFG 다듬기
10.1 ε-production rule 수를 줄이기 ... 134
10.2 CFG의 불필요한 symbol 제거하기 ... 138
10.3 CFG의 Normar Form(표준형식) ... 142
Chapter 11 CFG의 Ambiguity(모호성)
11.1 Parse Tree와 Ambiguity ... 149
11.2 CFG의 모호성 제거하기 ... 150
Chapter 12 Chomsky Hierarchy Ⅱ(정규포함 관계)
12.1 Pumping Lemma ... 159
12.2 Pumping Lemma 응용 ... 164
12.3 CFL를 위한 Pumping Lemma ... 167
12.4 CFL에 대한 Pumping Lemma : 응용 ... 168
Chapter 13 Parsing
13.1 정규 Derivation ... 174
13.2 LL(k) Parsing 전략 ... 175
13.3 LL(k) Parser 만들기 ... 180
13.4 LL(k) grammar 정의 ... 185
13.5 LR(k) Parsing 전략 ... 186
13.6 LR(k) Parser 만들기 ... 187
13.7 LR(k) Grammar(정의) ... 198
Chapter 14 Formal Language 응용
14.1 HyperText Markup Language(HTML) ... 200
14.2 XML과 Document-Type 정의 ... 201
14.3 LeX and YACC ... 204
Chapter 15 형식언어 및 오토마타 체계 Ⅲ
15.1 TM이 인식할 수 없는 언어 ... 211
15.2 Universal TM ... 215
15.3 Recursive Language와 Language Hierarchy ... 218
15.4 Characterization 증명 ... 226
더보기 닫기