Introduction
강의 목표 Finite Automata의 여러 가지 형태 및 각종 finite automata로 인식될 수 있는 언어의 클래스의 성질, context-free 문법과 pushdown automata, 그리고 Turing machine과 computablity, 그리고 complexity의 문제들을 다룬다. 추가로 context free grammar의 deterministic parsing에 관해서 다룰 수 있다.
선 수 과 목 CS204 Discrete Mathematics homepage
담 당 교 수 최광무, 전산학동 2427호, choe@kaist.ac.kr
강 의 교 재
  • 주교재
    • 교재명 : Introduction to Automata Theory, Language, and Computation (third edition)
    • 저자 : John E. Hopcroft, Rajeev Motwani, Jeffery D. Ullman
    • 출판사 : Addison Wesley
    • Homepage : http://www-db.stanford.edu/~ullman/ialc.html


  • 부교재
    • Problem solving in automata, language, and complexity, Ding-zhu Du, Ker-i Ko, Wiley interscience.
강 의 시 간 화, 목 13:00 ~ 14:30
강 의 장 소 정보전자동 2112호

  Grading & Schedule
Grading
출 석
숙제 & 프로젝트
중간고사
기말고사
합 계
25%
25%
25%
25%
100%
Schedule

아래의 스케줄은 대략적인 것으로 변경될 수 있음.

주제
강의 기간
교재 범위
Introduction
Mathematical Preliminaries
1주
chap1
Finite Automata
Regular Expression
Properties of Regular language
4~5주
chap2, chap3, chap4
Context-Free Grammar
Pushdown Automata
Properties of Context-Free Language
Parsing
5~6주

chap5, chap6, chap7

Lecture Notes

Computation Theory
2~3주
chap8, chap9
Complexity Theory
1~2주
chap10

  Exam.

  • 중간고사 :
  • 기말고사 :

  Materials & Homeworks

   - Notice -

  • Homework
    • 공 지
      숙제는 일주일에 한 번씩, 매주 목요일에 Course Homepage Materials & Homeworks Section을 통해 공지될 예정입니다.
    • Due
      공지된 다음 주 목요일 수업 시작 전(13:00)까지 입니다.
    • Delay
      Due 이후에 제출된 숙제는 일체 받지 않습니다.
    • 제출 방식
      제출 장소는 제 1 강의실 앞 숙제함이며,
      Report Format에 대한 다음 사항을 반드시 지켜 제출해 주시기 바랍니다.
      - 표지는 생략하고 첫 페이지의 상단 3Cm 정도의 공간에 숙제번호, 제출일, 학과, 전공, 학번, 이름을 기록합니다.

    • Solution 공지
      숙제에 대한 Solution은 해당 숙제의 Due가 있는 주말까지 Homepage를 통해 공지 됩니다.
    • 숙제 Return
      숙제 Due 일주일 후 금요일 수업 시간을 통해 채점된 숙제를 돌려 드리고, 성적은 Homepage를 통해 지속적으로 Update 되어 공지될 예정입니다.
  • 각 강의의 Lecture Note 및 TP는 해당 Chapter의 수업이 끝난후 제공됩니다.
  • Lecture Notes ( cf. 2008 CS322 Homepage)
    Number Date Week Day Topic
    01  2011/09/01   01(Thu)     Introduction - The History of Automata Theory
    02  2011/09/06   02(Tue)     The Central Concepts of Automata Theory
    03  2011/09/08   02(Thu)     Relation, Recursion, and Natural Number
    04  2011/09/15   03(Thu)     Uncountable & Finite State Automata
    05  2011/09/20   04(Tue)     FA & Definition of the language accepted by FA
    06  2011/09/22   04(Thu)     Extension of FA's
    07  2011/09/27   05(Tue)     NFA & e-NFA
    08  2011/09/29   05(Thu)     RE & e-NFA
    09  2011/10/04   06(Tue)     Equivalence of FA and RE
    10  2011/10/06   06(Thu)     Equivalence of FA and RE(2)
    11  2011/10/11   07(Tue)     Pumping Lemma
    12  2011/10/13   07(Thu)     Closure Properties of RL & Minimal DFA
    13  2011/10/18   08(Tue)     Minimal DFA
    14  2011/10/27   09(Thu)     Context-free Grammar
    15  2011/11/01   10(Tue)     Left & Right Most Derivation in CFG and Ambiguity of CFG
    16  2011/11/03   10(Thu)     Pushdown automata
    17  2011/11/08   11(Tue)     PDA & CFG
    18  2011/11/10   11(Thu)     Rewriting System & FA, Grammars and PDA
    19  2011/11/15   12(Tue)     Top Down & Bottom Up Parsing
    20  2011/11/17   12(Thu)     Turing Machine
    21  2011/11/22   13(Tue)     Turing Machine(2)
    22  2011/11/24   13(Thu)     Undecidability
    23  2011/11/30   14(Tue)     Turing-Church's Thesis(1)
    24  2011/12/01   14(Thu)     Turing-Church's Thesis(2)
    25  2011/12/06   15(Tue)     Turing-Church's Thesis(3)
    26  2011/12/08   15(Thu)     NP-completeness
    27  2011/12/13   16(Tue)     Context Free Language


  • TPs ( cf. 2011 CS322 Homepage)
    Chapter TP 최종수정일
    Chapter 00     Communications and Studying 2014-03-05
    Chapter 00     Introduction to Automata Theory, Languages, and Computation 2014-03-05
    Chapter 01     Automata - The Methods and the Madness 2014-03-05
    Chapter 01     [Supplementary TP1] Reviews on Discrete Mathmatics 2014-03-05
    Chapter 02     Finite Automata 2014-03-05
    Chapter 02     [Supplementary TP1] Repeated Composition of Functions 2014-03-05
    Chapter 02     [Supplementary TP2] Examples of Deterministic Finite Automata 2014-03-05
    Chapter 02     [Supplementary TP3] Korean Automata 2014-03-05
    Chapter 03     Regular Expressions and Languages 2014-03-05
    Chapter 04     Properties of Regular Languages 2014-03-05
    Chapter 05     Context-free Grammars 2014-03-05
    Chapter 05     [Supplementary TP1] Examples for Context-Free Grammars and Regular grammar 2014-03-05
    Chapter 06     Pushdown Automata 2014-03-05
    Chapter 06     [Supplementary TP1] Rewriting System - grammars, fa, and PDA 2014-03-05
    Chapter 07     Properties of Context-free Languages 2014-03-05
    Chapter 08     Introduction to Turing Machines 2014-03-05
    Chapter 08     [Supplementary TP1 - Martin's book Ch07] Turing Machines 2014-03-05
    Chapter 08     [Supplementary TP2 - Martin's book Ch08] Recursively Enumerable Languages 2014-03-05
    Chapter 09     Undecidability 2014-03-05
    Chapter 09     [Supplementary TP1] Computability 2014-03-05
    Chapter 09     [Supplementary TP2 - Martin's book Ch09] Undecidable Problms 2014-03-05
    Chapter 10     Intractable Problems 2014-03-05
    Chapter 10     [Supplementary TP1 - Martin's book Ch11] Introduction to Computational Complexity 2014-03-05


  • 한글 강의 노트
    Chapter Note 최종수정일
    Chapter 01     Overview of Lecture 2014-03-05
    Chapter 01     The Central Concepts of Automata Theory 2014-03-05
    Chapter 01     Elements of Discrete Mathmatics 2014-03-05
    Chapter 01     Recursion 2014-03-05
    Chapter 02     Finite State Automata 2014-03-05
    Chapter 02     Extension of Finite State Automata 2014-03-05
    Chapter 02     Extension of Finite State Automata(2) 2014-03-05
    Chapter 03     Regular Expression 2014-03-05
    Chapter 03     FA to RE(2) 2014-03-05
    Chapter 04     Properties of Regular Languages 2014-03-05
    Chapter 04     Closure Properties of Regular Languages 2014-03-05
    Chapter 05     Context-Free Grammar 2014-03-05
    Chapter 07     Useful grammar 2014-03-05
    Chapter 07     Pumping Lemma for CFL 2014-03-05
    Chapter 07     CYK Algorithm 2014-03-05
    Chapter 08     Turing Machine 2014-03-05
    Chapter 09     Undecidability 2014-03-05
    Chapter 09     Primitive recursive function 2014-03-05
    Chapter 09     Mu-recursive partial function 2014-03-05
    Chapter 10     NP-compleness 2014-03-05
    Chapter 10     Satisfiability Problem 2014-03-05


  • Homeworks/Exams
    Issue Date Homework(TA responsible) Solution
    2011/09/08 Homework 1(Kim, Tae-Joon)  
    2011/09/22 Homework 2(Kim, Tae-Joon)  
    2011/09/26 Program Homework(1 Kim, Tae-Joon, 2 Lee, Jong-Hyeob)  
    2011/09/29 Homework 3(Kim, Tae-Joon)  
    2011/10/13 Homework 4(Lee, Jonghyeob)  
    2011/10/27 Homework 5(Lee, Jonghyeob)  
    2011/11/03 Homework 6(Lee, Jonghyeob)  
    2011/11/10 Homework 7(Cha, Sanghoon)  
    2011/11/17 Homework 8(Cha, Sanghoon)  
    2011/11/24 Homework 9(Cha, Sanghoon)  
    2011/12/01 Homework 10(Cha, Sanghoon)  
    2011/12/08 Homework 11(Lee, Jonghyeob)  
  • Projects
    Issue Date Project(TA responsible)

  •   Attendance

        (출석 및 수업 참여는 매우 중요합니다.)

    Date Attendance
    01/2011/09 06.xls

      Assistant
    이      름
    연 구 실
    전화번호
    이   메   일
    담      당
    박창희
    조교장
    이상헌
    2422호
    bv@pllab.kaist.ac.kr
    이창재
    박민지
     

    CS322, http://adamant.kaist.ac.kr/cs322_2009, Webmaster: manip [at] pllab.kaist.ac.kr