[오토마타] 0. 목차

카이스트 CS322 형식언어 및 오토마타 공부 내용입니다.

정규언어

1. 유한 결정적 오토마타(DFA, Deterministic Finite Automata)

2. 유한 비결정적 오토마타(NFA, Non-deterministic Finite Automata)

3. DFA와 NFA의 동등성

4. 정규표현식과 NFA의 동등성

5. Pumping Lemma

6. 정규언어의 폐쇄성(Closure)과 동등성

7. 정규언어의 최소화

8. 마이힐-네로드 정리(Myhill-Nerode Theorem)

9. Monadic Second-Order Logic(MSO)

 

문맥 자유 언어

10. 문맥 자유 언어(Context Free Language) 

11. 푸쉬다운 오토마타(PDA, Pushdown Automata)

12. PDA와 CFG의 동등성

13. CFG의 폐쇄성

14. Pumping Lemma For CFG

 

튜링머신

15. 결정 가능한 문제(Decidable Problem)

16. 튜링머신

17. 변형된 튜링머신

18. 범용 튜링머신(Universal TM)

.... 추가중