Course Information

• Class Name: Special Topics in Automata

• Time/Room: 

• Credit: 3

• Course Code: 

• Course Classification: Basic Common
  

• Instructors: In Jeong Chung (Primary Instructor)

• Email: chung@korea.ac.kr

• Homepage: http://iis.korea.ac.kr

• Office: 7-301

Teaching Assistant

• Name: Sumin Son(손수민)
• Department: Computer and Information Science
  
• E-mail: ssm5257@korea.ac.kr
  
• Office: 7-302
  
• Tel.: 044-860-1342
  

Notice

• Mid-term exam
• 10월 23일 (수) 수업시간

• Final exam
• 12월 18일(수) 수업시간

Assignment(s)

•  ASSIGNMENT
  
• 제출 방법
• 제출 장소 : 제 2 과학기술관 3층 컴퓨터정보학과 도서실(7-313) 앞  오토마타 과제 제출함
  
• 제출시 학번,이름 필수(학번,이름 미기재로 인한 불이익은 조교가 책임지지 않습니다)
• 제출기한을 지나서 지각 제출 할 경우 점수에 패널티가 부여됩니다.
• 과제 제출에 있어 부정행위가 발견되면 0점 처리됩니다.

• 1. 2019automatahw1.hwp 제출 기한 : 2019 10 18 (금)
• 2. 2019hw2.hwp 제출기한 : 2019 11 20 (수)
• 3. hw3.docx

• PROGRAMMING ASSIGNMENT
• 제출 방법
• 파일명 예시 : 오토마타_프로그래밍1차과제_학번_이름.zip 형태로 압축하여  과제 제출 전용 이메일(iislab.son.gmail.com)으로 제출 (연락용 이메일과 혼동 주의!  과제 제출용 메일은 과제제출만 부탁드립니다.)
  
• 각각의 문제에 대한 코드 파일 + 결과물 스크린샷이 포함되어 있어야 합니다.
  
• 제출기한을 지나서 지각 제출 할 경우 점수에 패널티가 부여됩니다.
• 과제 제출에 있어 부정행위가 발견되면 0점 처리됩니다.

Textbook(s)

• Sipser, Introduction to the Theory of Computation (3rd Ed.), Cengage Course Technology, 2012

Weekly Content Plan

1. [09.01-09.07] Introduction (Finite Automata) Pre.ppt

2. [09.08-09.14] FSA(Finite (Pushdown Automata) State Automata) Finite Automata and Regular Expression.ppt  

3. [09.15-09.21] FSA(Finite State Automata)

4. [09.22-09.28] FSA(Finite State Automata)

5. [09.29-10.05] Regular Grammar, Regular Expression Closure Properties of Regular Language.ppt

6. [10.06-10.12] PDA(Push Down Automata), CFL Pushdown Automata.ppt  

7. [10.13-10.19] PDA(Push Down Automata), CFL Features of Context-Free Language.ppt

8. [10.20-10.26] Review and Mid-term Exam

9. [10.27-11.02] Turing Machines Turing Machine.ppt
   TM#1 (Definition of TM).pptx ,TM#2 (Configuration of TM).pptx ,TM#3 (Problem Reduction).pptx
10. [11.03-11.09] Determinism and Nondeterminism Turing Machine and Undecidability.ppt
11. [11.10-11.16] Type 0 Grammar, Recursive Languages, Recursive Enumerable Languages
12. [11.17-11.23] Chomsky Hierarchy, Decision Problems Chomsky Hierarchy.pptx
13. [11.24-11.30] Class P and Class NP NP-Complete.pptx
14. [12.01-12.07] Problem Reduction, NP-Completeness
15. [12.08-12.14] Cook Theorem
16. [12.15-12.21] Review and Final-term Exam