강 의 소 개
모국어 강의 본 강의는 모국어로 이루어진다. English lecture will be provided in the next year by Prof. Otfried
강 의 개 요 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


  • 부교재
    • 1. Introduction to Automata Theory, Language, and Computation, John E. Hopcroft and Jeffery D. Ullman (second edition) → 예전 교재로 책이 잘 쓰여져 있음.
    • 2. Introduction to Languages and the Theory of Computation, John Martin (forth editon) → TP가 잘 정리되어 있음.
    • 3. Problem solving in automata, language, and complexity, Ding-zhu Du, Ker-i Ko, Wiley interscience.
    • -> 좋은 연습문제가 많음.
강 의 시 간 화, 목 13:00 ~ 14:30
강 의 장 소 정보전자동 2112호

  강 의 계 획
성 적
출 석
숙제 & 프로젝트
중간고사
기말고사
합 계
25%
25%
25%
25%
100%
강 의 일 정
주제
강의 기간
교재 범위
Ⅰ. Mathematical Preview
2주
chap1
Ⅱ. Finite Automata, Regular expression, Pumping Lemma for RL, mDFA
4주
chap2, chap3, chap4
Ⅲ. CFG, Pushdown Automata, Left/Right Parser, CNF, and CYK Algorithm
4주
chap5, chap6, chap7
Ⅳ. Turing Machine, non-RE and Church’s thesis
3주
chap8, chap9
Ⅴ. Complexity Theory
1주
chap10

  시 험

  • 중간고사 : 10월 23일 화요일 오후 1:00 - 3:00, 전산동 1501호(제 1공동 강의실) Solution
  • 기말고사 : 12월 18일 화요일 오후 1:00 - 4:00

  강의자료

   - Notice -

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

    • Solution 공지
      숙제에 대한 Solution은 해당 숙제 Due가 있는 주말까지 Homepage를 통해 공지 됩니다.
    • 숙제 Return
      숙제 Due 일주일 후 금요일 수업 시간을 통해 채점된 숙제를 돌려 드리고, 성적은 Homepage를 통해 지속적으로 Update 되어 공지될 예정입니다.


  • 강의 필기 ( cf. 2011 CS322 Homepage)
    Number Week Day Topic Date
    00    01(Tue)     Formal Language and Automata Theory 2012/09/04
    01    01(Thu)     Reviews on Discrete Math 2012/09/06
    02    02(Tue)     Reviews on Discrete Math(2) 2012/09/11
    03    02(Thu)     Basics of Language Theory 2012/09/13
    04    03(Tue)     Deterministic Finite State Automata 2012/09/18
    05    03(Thu)     DFA and extension of FA 2012/09/20
    06    04(Tue)     NFA and (epsilon)-NFA 2012/09/25
    07    04(Thu)     Finite State Automata 2012/09/27
    08    05(Thu)     Regular Expression 2012/10/04
    09    06(Tue)     Mealy Machine and Hangeul Automata 2012/10/09
    10    06(Thu)     Pumping Lemma 2012/10/11
    11    07(Tue)     m-DFA and Context-Free Grammar 2012/10/16
    12    07(Thu)     Context-Free Grammar(2) 2012/10/18
    13    09(Tue)     PushDown Automata 2012/10/30
    14    09(Thu)     CFG and Parse Tree 2012/11/01
    15    10(Tue)     PDA(2) and Properties of CFL 2012/11/06
    16    10(Thu)     LR Parser and Rewriting System 2012/11/08
    17    11(Tue)     Chomsky Normal Form and Pumping Lemma 2012/11/13
    18    11(Thu)     Chomsky Normal Form and Pumping Lemma(2) 2012/11/15
    19    12(Tue)     Turing Machine 2012/11/20
    20    12(Thu)     Turing Machine(2) 2012/11/22
    21    13(Tue)     Programming Technique 2012/11/27
    22    13(Thu)     Turing-Church Thesis 2012/11/29
    23    14(Tue)     Turing-Church Thesis(2) 2012/12/04
    24    14(Thu)     Undecidability 2012/12/06
    25    15(Tue)     Rice and Cook Theorem 2012/12/11
    26    15(Thu)     Cook Theorem(2) 2012/12/13


  • 교과서 TP ( cf. 2011 CS322 Homepage)
    Chapter 보조 TP 제목 최종수정일
    Chapter 00     Introduction to Automata Theory, Languages, and Computation 2014-03-05
    Chapter 01     Automata - The Methods and the Madness 2014-03-05
    1     Reviews on Discrete Mathmatics 2014-03-05
    Chapter 02     Finite Automata 2014-03-05
    1     Repeated Composition of Functions 2014-03-05
    2     Examples of Deterministic Finite Automata 2014-03-05
    3     한글오토마타 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
    1     Examples for Context-Free Grammars and Regular grammar 2014-03-05
    Chapter 06     Pushdown Automata 2014-03-05
    1     Left and Right parser 2014-03-05
    Chapter 07     Properties of Context-free Languages 2014-03-05
    Chapter 08     Introduction to Turing Machine 2014-03-05
    Chapter 09     Undecidability 2014-03-05
    1     Computability 2014-03-05
    Chapter 10     Intractable Problem 2014-03-05


  • 한글 강의 노트
    Chapter Secetion Note 최종수정일
    Chapter 01 1     언어와 오토마타이론 발전사와 강의순서 2014-03-05
    2     이산 수학 복습 2014-03-05
    2-1     증명 2014-03-05
    3     Recursion 혹은 수학적 귀납법과 무한집합 2014-03-05
    4     언어이론(Language Theory) 기초 2014-03-05
    Chapter 02 1     Deterministic Finite Automata 2014-03-05
    2     DFA의 확장 - Partial function 과 NFA 2014-03-05
    3     DFA의 확장(2) - ε-NFA와 Extended FA 2014-03-05
    4     한글 모아쓰기 오토마타 2014-03-05
    Chapter 03 1     Regular Expression과 Regular Language 2014-03-05
    2     Regular expression의 연립방정식을 이용한 해법 2014-03-05
    Chapter 04 1     정규(Regular) 언어를 위한 Pumping Lemma 2014-03-05
    2     정규(Regular) 언어에 관하여 닫혀있는 성질(closure property)과 대수계(algebraic system) 2014-03-05
    3     Myhill-Nerode Theorem and Minimization of DFA 2014-03-05
    Chapter 5 1     Context-Free Gramma 2014-03-05
    Chapter 7 1     Useful grammar 2014-03-05
    2     Chomsy Normal Form 2014-03-05
    3     Loop Invariance(보충) 2014-03-05
    4     CFL를 위한 Pumping Lemma 2014-03-05
    5     CYK 알고리즘 2014-03-05
    Chapter 8 1     Turing Machine 2014-03-05
    2     Turing Machine의 확장 1970-01-01
    Chapter 9 1      Undecidability 2014-03-05
    2     Primitive recursive function 2014-03-05
    3     mu-recursive partial function 2014-03-05


  • 강의 영상
    강의날짜 Week Day Video
    2012/09/04 01(Tue)     강의 개요
    2012/09/06 01(Thu)     Reviews on Discrete Mathmatics
    2012/09/11 02(Tue)     Reviews on Discrete Mathmatics(2)
    2012/09/13 02(Thu)     언어이론 기초(1)
    2012/09/13 02(Thu)     언어이론 기초(2)
    2012/09/13 02(Thu)     Countable & Uncountable infinite set
    2012/09/18 03(Tue)     DFA의 정의(1)
    2012/09/18 03(Tue)     DFA의 정의(2)
    2012/09/20 03(Thu)     DFA의 확장
    2012/09/20 03(Thu)     FA의 확장
    2012/09/20 03(Thu)     Non-Deterministic Finite Automata
    2012/09/25 04(Tue)     NFA와 ε-NFA
    2012/09/25 04(Tue)     NFA와 ε-NFA(2)
    2012/09/27 04(Thu)     Finite Automata
    2012/09/27 04(Thu)     Regular expression과 Regular Language
    2012/10/04 05(Thu)     Regular expression의 성질
    2012/10/04 05(Thu)     Regular expression의 해법
    2012/10/09 06(Tue)     한글 모아쓰기 오토마타
    2012/10/11 06(Thu)     Pumping Lemma for Regular Language(1)
    2012/10/11 06(Thu)     Pumping Lemma for Regular Language(2)
    2012/10/11 06(Thu)     Regular expression의 연립방정식 해법
    2012/10/16 07(Tue)     2012.10.16-1st.
    2012/10/16 07(Tue)     2012.10.16-2nd
    2012/10/16 07(Tue)     2012.10.16-3d
    2012/10/18 07(Thu)     2012.10.18-1st.
    2012/10/18 07(Thu)     2012.10.18-2nd
    2012/10/18 07(Thu)     2012.10.18-3d
    2012/10/30 09(Tue)     2012.10.30-1st
    2012/10/30 09(Tue)     2012.10.30-2nd
    2012/11/01 09(Thu)     2012.11.01-1st
    2012/11/01 09(Thu)     2012.11.01-2nd
    2012/11/06 10(Tue)     2012.11.06-1st
    2012/11/06 10(Tue)     2012.11.06-2nd
    2012/11/06 10(Tue)     2012.11.06-3d
    2012/11/08 10(Thu)     2012.11.08-1st
    2012/11/08 10(Thu)     2012.11.08-2nd
    2012/11/08 10(Thu)     2012.11.08-3d
    2012/11/13 11(Tue)     2012.11.13-1st
    2012/11/13 11(Tue)     2012.11.13-2nd
    2012/11/15 11(Thu)     2012.11.15
    2012/11/20 12(Tue)     2012.11.20
    2012/11/20 12(Tue)     2012.11.20
    2012/11/22 12(Thu)     2012.11.22
    2012/11/22 12(Thu)     2012.11.22
    2012/11/27 13(Tue)     2012.11.27
    2012/11/27 13(Tue)     2012.11.27
    2012/11/29 13(Thu)     2012.11.29
    2012/11/29 13(Thu)     2012.11.29
    2012/12/04 14(Tue)     2012.12.04
    2012/12/04 14(Tue)     2012.12.04
    2012/12/06 14(Thu)     2012.12.06
    2012/12/06 14(Thu)     2012.12.06
    2012/12/06 14(Thu)     2012.12.06


  • 부교재 Martin책의 TP
    Chapter 제목 최종수정일
    Chapter 01     Mathematical Tools and Techniques 2014-03-05
    Chapter 02     Finite Automata and the Languages They Accept 2014-03-05
    Chapter 03     Regular Expressions, Nondeterminism, and Kleene’s Theorem 2014-03-05
    Chapter 04     Context-Free Languages 2014-03-05
    Chapter 05     Pushdown Automata 2014-03-05
    Chapter 06     Context-Free and Non-Context-Free Languages 2014-03-05
    Chapter 07     Turing Machine 2014-03-05
    Chapter 08     Recursively Enumerable Languages 2014-03-05
    Chapter 09     Undecidable Problem 2014-03-05
    Chapter 10     Computable Functions 2014-03-05
    Chapter 11     Introduction to Computational Complexity 2014-03-05



  • 숙제
  • 숙제
    Issue Date Due Date Homework Solution TA
    2012/09/06 2012/09/16     Homework 1(Problem02Revised)     Solution 1 이창재
    2012/09/13 2012/09/20     Homework 2      이창재
    2012/09/20 2012/09/27     Homework 3     Solution 3 박민지, 정진영
    2012/09/27 2012/10/04     Homework 4     Solution 4 박민지, 정진영
    2012/10/04 2012/10/12     Homework 5     Solution 5 박민지, 정진영
    2012/10/11 2012/10/18     Homework 6     Solution 6 박민지, 정진영
    2012/11/01 2012/11/08     Homework 7     Solution 7 이상헌, 김태훈
    2012/11/08 2012/11/15     Homework 8     Solution 8 이상헌, 김태훈
    2012/11/15 2012/11/22     Homework 9     Solution 9 이상헌, 김태훈
    2012/11/22 2012/11/29     Homework 10     Solution 10 박창희
    2012/11/29 2012/12/06     Homework 11      박창희
    2012/12/06 2012/12/13     Homework 12      박창희


  • 프로젝트
    Issue Date Due Date Project TA
    2012/09/13 2012/09/27     Project 1-1 박민지, 정진영
    2012/09/25 2012/10/10     Project 1-2 박민지, 정진영
    2012/09/25 2012/10/17     Project 2-1 이상헌, 김태훈
    2012/10/04 2012/11/08     Project 1 박민지, 정진영
    2012/10/11 2012/11/28     Project 2 이상헌, 김태훈
    2012/10/11 2012/12/12     Final Project 이상헌


  •   출 석 현 황


  • 노아 게시판에서 출석 확인하세요.
  • Date Attendance
    2012/12/6 Attendance(Nov).xls
    2012/12/6 Attendance(SepOct).xls

      조 교
    이      름
    연 구 실
    전화번호
    이   메   일
    담      당
    박창희
    전산동 4409호
    x7738
    changhee.park@kaist.ac.kr
    조교장
    이상헌
    전산동 2422호
    x7720
    bv@pllab.kaist.ac.kr
    홈페이지 관리
    이창재
    전산동 2430호
    x7833
    mettugi@kaist.ac.kr
    출석 관리
    박민지
    KI빌딩 C304
    x7763
    friendpe@kaist.ac.kr
    정진영
    전산동 4422호
    x7788
    jinjung010@gmail.com
    김태훈
    전산동 4414호
    x7815
    thkim@calab.kaist.ac.kr
     

    CS322, http://adamant.kaist.ac.kr/cs322, Webmaster: bv [at] pllab.kaist.ac.kr