강 의 소 개
모국어 강의 본 강의는 모국어로 이루어진다.
강 의 개 요 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:15
    강 의 장 소 창의학습관(E11) 311호

    강 의 계 획
    성 적
    25%
    25%
    25%
    25%
    100%
    강 의 일 정
    주제
    강의 기간
    교재 범위
    Ⅰ. Mathematical Preview
    2주
    chap1
    Ⅱ. Finite Automata, Regular expression, Pumping Lemma for Regular Languages, minimal DFA
    4주
    chap2, chap3, chap4
    Ⅲ. CFG, Pushdown Automata, Left/Right Parser, CNF, and CYK Algorithm
    4주
    chap5, chap6, chap7
    Ⅳ. Turing Machine, non-Recursively Enumerable and Church’s thesis
    3주
    chap8, chap9
    Ⅴ. Complexity Theory
    1주
    chap10

    ※공휴일과 강의 상황에 따라 약간 바뀔 수 있습니다.

    시 험
    • 중간고사 : 10월 21일 화요일 오후 1:00 - 3:00 ***전산동 1501호(제 1공동 강의실)***문제와 정답 중간고사 성적
      • 중간고사 성적이 나왔습니다.
        문의 또는 확인할 사항이 있으신 분은 Office Hour 시간(화, 목 오후 4:00~5:30)에 N1 405호로 오시면 됩니다.

      문제별 담당 조교
      1번: 이윤석 조교님
      2번: 박지훈 조교님
      3번: 이의현 조교님
      4번: 이광희 조교님
      5번: 오교중 조교님
      6번: 이창훈 조교님
      7번: 이의현 조교님

      오피스아워 시간에 오시지 못하시는 분들은 월, 수, 금 오후 2:30~4:00 에 N1 724호로 오시거나, 오교중 조교(aomaru@kaist.ac.kr)에 연락주세요.
      중간고사 시험지 확인은 N1 724호로 오시거나, 오교중 조교(aomaru@kaist.ac.kr)에 연락주세요.

    • 기말고사 : 12월 16일 화요일 오후 1:00 - 3:00 ***전산동 1501호(제 1공동 강의실)***

      기말고사 컴플레인은 12월 24일(수요일) 까지 받습니다.

      문제별 담당 조교
      1번: 이의현 조교님 (E3 2422)
      2번: 이창훈 조교님 (E3 4441)
      3번: 오교중 조교님 (N1 724)
      4번: 이윤석 조교님 (E3 3443)
      5번: 이광희 조교님 (E3 3416)
      6번: 박지훈 조교님 (N1 524)
      7번: 최광무 교수님

      해당 문제별로 조교님에게 각각 문의하시기 바랍니다.

      • 시험은 Open Book으로 시행 됩니다. 전자기기는 통신을 할 수 있으므로 시험 중에 금지합니다.

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

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

  • 강의 필기 ( cf. 2012 CS322 Homepage)
    번호 주(요일) 제목 최종수정일
    01
    01(Tue)
    소개, 이산수학 복습
    2014-09-02
    02
    01(Thur)
    이산수학 복습 계속
    2014-09-04
    03
    02(Thur)
    무한집합
    2014-09-11
    04
    03(Tue)
    Uncountable과 언어이론 기초
    2014-09-16
    05
    03(Thur)
    Terminologies in LT & DFA
    2014-09-18
    06
    04(Tue)
    DFA
    2014-09-23
    07
    04(Thur)
    NFA
    2014-09-25
    08
    05(Tue)
    Extension of FAs
    2014-09-30
    09
    05(Thur)
    Extended FA & FA to RE
    2014-10-02
    10
    06(Tue)
    Regular Languages
    2014-10-07
    11
    07(Tue)
    한글 정규언어의 성질 & Context Free Grammar
    2014-10-14
    12
    07(Thur)
    Derivation of CFG
    2014-10-16
    13
    09(Tue)
    Parse Tree Revisited
    2014-10-28
    14
    09(Thur)
    CFG=PDA
    2014-10-30
    15
    10(Tue)
    PDA2
    2014-11-04
    16
    10(Thur)
    Properties of Context Free Languages
    2014-11-06
    17
    11(Tue)
    Pumping Lemma for CFG & CYK algorithm
    2014-11-11
    18
    11(Thur)
    Pumping Lemma for CFG & CYK algorithm 2
    2014-11-13
    19
    12(Tue)
    Introduction to Turing Machine
    2014-11-18
    20
    12(Thur)
    Dijkstra's mini language & loop invariance
    2014-11-20
    21
    13(Tue)
    Extension & Restriction of TM, Undecidability
    2014-11-25
    22
    13(Thur)
    Turing Church's Thesis & Computability
    2014-11-27
    23
    14(Tue)
    (Partial) Recursive Function Theory
    2014-12-02
    24
    14(Thur)
    m-recursive ftn & Turing Church's THesis
    2014-12-04
    25
    15(Tue)
    NP-complete & SAT & Intractable Problems
    2014-12-09

  • 교과서 TP ( cf. 2012 CS322 Homepage)
    챕터 보조 TP 제목 쪽수 최종수정일
    Chapter 00
    Introduction to Automata Theory, Languages, and Computation
    2
    2014-08-19
    Chapter 01
    Automata - The Methods and the Madness
    18
    2014-08-19
    1
    Reviews on Discrete Mathmatics
    25
    2014-08-19
    Chapter 02
    Finite Automata
    27
    2014-10-01
    1
    Repeated Composition of Functions
    4
    2014-09-18
    2
    Examples of Deterministic Finite Automata
    6
    2014-09-18
    3
    한글오토마타
    5
    1970-01-01
    4
    FA with Output
    2
    2014-10-01
    Chapter 03
    Regular Expressions and Languages
    16
    2014-09-27
    Chapter 04
    Properties of Regular Languages
    24
    2014-09-27
    Chapter 05
    Context-free Grammars
    16
    2014-10-28
    1
    Examples for Context-Free Grammars and Regular grammar
    15
    2014-09-27
    Chapter 06
    Pushdown Automata
    12
    2014-10-28
    Chapter 07
    Properties of Context-free Languages
    2014-11-05
    Chapter 08
    Introduction to Turing Machine
    2014-11-05
    Chapter 09
    Undecidability
    2014-11-29
    1
    Computability
    2014-11-29
    2
    Partial Recursive Functions
    2014-11-27
    Chapter 10
    Intractable Problem
    2014-11-05
    1
    NP complete 문제는 수학인가
    2014-11-05
    Chapter X
    Dijkstra의 Guarded Command Set
    2014-11-22
    1
    Guarded Commands, Nondeterminacy and Formal Derivation of Programs
    2014-11-20
    Chapter Y
    2012 SIGPL 겨울학교
    2014-12-09
    1
    2012 SIGPL 겨울학교 - 책갈피 (ppt)
    2014-12-09

  • 한글 강의 노트 ( cf. 2012 CS322 Homepage)
    챕터 섹션 제목 쪽수 최종수정일
    Chapter 1
    1
    언어와 오토마타이론 발전사와 강의순서
    4
    2014-09-03
    2
    이산 수학 복습
    6
    2014-08-19
    3
    증명
    7
    2014-10-23
    4
    Recursion 혹은 수학적 귀납법과 무한집합
    4
    2014-10-23
    5
    언어이론(Language Theory) 기초
    3
    2014-10-23
    Chapter 2
    1
    Deterministic Finite Automata
    4
    2014-10-23
    2
    DFA의 확장 - Partial function 과 NFA
    4
    2014-10-23
    3
    DFA의 확장(2) - ε-NFA와 Extended FA
    3
    2014-10-23
    4
    한글 모아쓰기 오토마타
    3
    2014-10-23
    Chapter 3
    1
    Regular Expression과 Regular Language
    3
    2014-10-23
    2
    Regular expression의 연립방정식을 이용한 해법
    3
    2014-10-23
    Chapter 4
    1
    정규(Regular) 언어를 위한 Pumping Lemma
    4
    2014-10-23
    2
    정규(Regular) 언어에 관하여 닫혀있는 성질(closure property)과 대수계(algebraic system)
    3
    2014-10-23
    3
    Myhill-Nerode Theorem and Minimization of DFA
    3
    2014-10-23
    Chapter 5
    1
    Context-Free Gramma(문맥자유 문법)
    4
    2014-10-23
    Chapter 6
    1
    Pushdown Automata
    4
    2014-10-28
    Chapter 7
    1
    Useful grammar
    2014-11-05
    2
    Chomsy Normal Form
    2014-11-05
    3
    Loop Invariance(보충)
    2014-11-05
    4
    CFL를 위한 Pumping Lemma
    2014-11-05
    5
    CYK 알고리즘
    2014-11-05
    Chapter 8
    1
    Turing Machine
    2014-11-26
    2
    Turing Machine의 확장
    2014-11-26
    Chapter 9
    1
    Undecidability
    2014-11-26
    2
    Primitive recursive function
    2014-11-26
    3
    mu-recursive partial function
    2014-11-26
    Chapter 10
    1
    NP-compleness
    2014-11-26
    2
    Satisfiability Problem
    2014-11-26

  • 부교재 Martin책의 TP
    Chapter 제목 쪽수
    Chapter 01
    Mathematical Tools and Techniques
    56
    Chapter 02
    Finite Automata and the Languages They Accept
    42
    Chapter 03
    Regular Expressions, Nondeterminism, and Kleene’s Theorem
    25
    Chapter 04
    Context-Free Languages
    31
    Chapter 05
    Pushdown Automata
    39
    Chapter 06
    Context-Free and Non-Context-Free Languages
    23
    Chapter 07
    Turing Machine
    42
    Chapter 08
    Recursively Enumerable Languages
    35
    Chapter 09
    Undecidable Problem
    30
    Chapter 10
    Computable Functions
    42
    Chapter 11
    Introduction to Computational Complexity
    27
  • 숙 제
  • 필기숙제
    Issue Date Due Date Homework Solution TA
    2014/09/11
    2014/09/18
    이광희, 이의현
    2014/09/18
    2012/09/25
    이광희, 이의현
    2012/09/25
    2012/10/02
    이광희, 이의현
    2012/10/02
    2012/10/13
    이광희, 이의현
    2012/10/31
    2012/11/06
    오교중, 이창훈
    2012/11/06
    2012/11/13
    오교중, 이창훈
    2012/11/12
    2012/11/20
    이창훈, 오교중
    2012/11/24
    2012/11/30
    오교중, 이창훈
    2012/11/27
    2012/12/04
    박지훈, 이윤석
    2012/12/04
    2012/12/11
    박지훈, 이윤석
    • 숙제 제출은 매주 목요일 수업시간 전에 일괄 수거합니다. 미리 내시거나, 늦게 내시는 분은 "Office Hour 시간: 화/목 16:00~17:30 N1 #405" 또는
    • 숙제 #1,2,3,4 는 E3-1 2422호 앞 숙제함에 제출해 주시고, 숙제 #5 부터는 N1 4층 "CS322-Formal Languages and Automata" 숙제함에 제출해 주세요.
    • 11월 20일 휴강 여부와 상관없이 숙제 7번은 N1 4층 숙제함으로 제출해 주세요.

  • 프로젝트
    Issue Date Due Date Project TA
    2014/09/23
    2014/10/08
    Project 1-1 DFA 시뮬레이터
    이의현
    2014/10/01
    2014/10/15
    Project 1-2 Mealy machine 시뮬레이터
    최광무
    2014/10/11
    2014/11/05
    Project 1 한글모아쓰기 오토마타
    최광무
    2014/10/15
    2014/11/19
    Project 2-1 e-NFA to m-DFA 변환기
    최광무
    2014/11/04
    2014/11/26
    Project 2 정규식이 나타내는 언어를 받아들이는 m-DFA 만들기
    최광무
    2014/11/25
    2014/12/10
    Project 3 3×4 한글자판을 위한 한글모아쓰기 오토마타
    최광무
    • 프로젝트 재제출은 12월 17일 수요일 까지 받습니다.


  • 프로젝트 참고자료
    Issue Date File Name Details
    2014/10/20
    Bison과 Flex의 소개 및 사용법
    2012/10/20
    Lex & Yacc의 소개 및 사용법
  • 조 교 정 보
    • 조교 Office Hour: (Tuesday, Thursday) 16:00~17:30, N1 #405

    이 름 연 구 실 전화번호 이 메 일 담 당
    오교중
    N1 724
    010-9379-1386
    aomaru@kaist.ac.kr
    조교장, 홈페이지
    박지훈
    N1 524
    010-6851-7595
    jhpark@se.kaist.ac.kr
    이의현
    E3 2422
    010-2568-5236
    luh0907@kaist.ac.kr
    출석
    이광희
    E3 3416
    010-9977-4322
    kh0611@kaist.ac.kr
    이창훈
    E3 4441
    010-5501-3383
    changhoon@nclab.kaist.ac.kr
    이윤석
    E3 3443
    010-3595-0837
    kstylee@gmail.com

    출 석 현 황
    • 노아 보드에서 해당 날짜의 자리 확인 후 출석 체크 하세요.
      • 출석 현황 업데이트는 12월 17일 수요일 까지 받습니다.

    • CS322 2014 출석표 → 클라우드 저장소에 저장된 최신 정보 반영 정보입니다.

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