계산모델 : 오토마타 및 형식언어

Chapter 1 준비(Preliminaries)
표기관계
증명법
-연습문제

Chapter 2 형식언어(Formal Languages)
Rule에 의한 언어 생성
Definition : Formal Languages and Grammars
문법과 언어 예
-연습문제

Chapter 3 기타 언어 표현 모델
L-system
syntax Flow Graph
Regular Expression
-연습문제

Chapter 4 결정성 오토마타
Deterministic Turing Machiness(경정성 투어링 장치)
Deterministic Linear Bounded Automata(DLBA)
Deterministic Pushdown Automata(DPDA)
Deterministic Finite Automata(DFA)
-연습문제

Chapter 5 비결정성 오토마타(Nondeterministic Automata)
Nondeterministic Finite Automata(NFA)
Nondeterministic Pushdown Automata(NPDA)
Nondeterministic Turing Machines(NTM) 및 Nondeterministic Linear Bounded Automata(NLBA)
Nondeterministic Algorithms
NFA와 e-transitions
FA의 e-transitions 제거하기
-연습문제

Chapter 6 여러 형태의 Automata
Transducers:출력이 있는 Atomata
여러 형태의 TM
여러 형태의 PDA
여러 형태의 FA
Church;s Hypothesis
-연습문제

Chapter 7 언어 및 오토마타 체계 1
Chomsky Hierarchy
Characterization(특성화 관계) 증명
-연습문제

Chapter 8 FA 다듬기
NFA를 DFA로 전환하기
DFA를 최소화 하기
-연습문제

Chapter 9 형식언어의 특성(Properties of the Formal Languages)
Regular Language의 특성
Context-free Language의 특성
-연습문제

Chapter 10 CFG 다듬기
ε-Production Rule 제거하기
Unit Production Rule 제거하기
CFG의 불필요한 Symbol 제거하기
-연습문제

Chapter 11 CFG의 Ambiguity(모호성)
Parse Tree
Parse Tree와 CFG의 Amviguity
CFG의 모호성 제거하기
-연습문제

Chapter 12 Chomsky Hierarchy 2(정규포함 관계)
포함관계
Pumping Lemma
Pumping Lemma 응용
CFL에 대한 Pumping Lemma
CFL에 대한 Pumping Lemma 응용
Ogden's Lemma
CFL에 대한 Pumping Lemma 증명
-연습문제

Chapter 13 Parsing
Derivation
LL(k) Parsing 전략
LL(k) Parsing 만들기
LR(k) Parsing 전략
LR(k) Grammar(정의)
-연습문제

Chapter 14 Formal Language 응용
Hyper Text Markup Languge(HTML)
DTD와 XML
Gene Grammar(유전자 문법)
Lex and YACC

Chapter 15 형식언어 및 오토마타 체계 3
TM이 인식할 수 없는 언어
Universal TM
Enumerble Language
Recursive Language
Characterization 증명
-연습문제

Appendix