강 의 소 개
모국어 강의 본 강의는 모국어로 이루어진다.
강 의 개 요 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

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

    시 험

    강 의 자 료
    • TP와 한글강의노트는 강의 전에 미리 올라옵니다. 미리 읽어보고 인쇄하여 강의에 반드시 들고 오시길 바랍니다.
    • 강의 필기는 수업이 끝난 직후 제공됩니다.
    • 이전 년도 강의 자료들을 참고하셔서 공부하시길 권장드립니다. 2007 2008 2009 2011 2012 2014 2015 2016

  • 강의 필기 ( cf. 2016 CS322 Homepage)
    파트 챕터 강의순서 강의일 제목
    Part I
    Chapter 1
    제 1강
    2016-09-01(목)
    제 2강
    2016-09-06(화)
    제 3강
    2016-09-08(목)
    제 4강
    2016-09-13(화)
    Part II
    Chapter2
    제 5강
    2016-09-20(화)
    제 6강
    2016-09-22(목)
    제 7강
    2016-09-27(화)
    제 8강
    2016-09-29(목)
    Chapter3
    제 9강
    2016-10-04(화)
    제 10강
    2016-10-06(목)
    Chapter4
    제 11강
    2016-10-11(화)
    제 12강
    2016-10-13(목)
    Part III
    Chapter5
    제 13강
    2016-10-18(화)
    제 14강
    2016-10-27(목)
    Chapter6
    제 15강
    2016-11-01(화)
    Chapter7
    제 16강
    2016-11-03(목)
    제 17강
    2016-11-08(화)
    제 18강
    2016-11-10(목)
    제 19강
    2016-11-15(화)
    제 20강
    2016-11-17(목)
    제 21강
    2016-11-22(화)
    Part IV
    Chapter8
    제 22강
    2016-11-24(목)
    제 23강
    2016-11-29(화)
    Chapter9
    제 24강
    2016-12-01(목)
    제 25강
    2016-12-06(화)

  • 교과서 TP ( cf. 2016 CS322 Homepage)
    파트 챕터 보조 TP 제목 쪽수 최종수정일
    Part I
    Chapter 0
    Introduction to Automata Theory, Languages, and Computation : v1
    2
    2016-09-02
    Chapter 1
    Automata - The Methods and the Madness : v1
    18
    2016-09-02
    1
    Reviews on Discrete Mathmatics : v1 v2 v3
    26
    2016-09-20
    Part II
    Chapter 2
    Finite Automata : v1 v2 v3
    33
    2016-09-29
    1
    FA Composition : v1
    4
    2016-09-14
    2
    FA Deterministic Finite Automata : v1
    8
    2016-09-14
    3
    FA with output : v1
    3
    2016-09-14
    4
    한글 모아쓰기 DFA : v1
    6
    2016-09-14
    Chapter 3
    Regular Expressions and Languages : v1 v2
    17
    2016-10-07
    Chapter 4
    Properties of Regular Languages : v1 v2
    28
    2016-10-12
    Part III
    Chapter 5
    Context-Free Grammars : v1 v2
    16
    2016-10-28
    A
    Examples of Context-Free Grammars : v1
    10
    2016-10-12
    B
    Finite Automata and Regular Grammars, and Context-free Grammars : v1 v2
    10
    2016-11-11
    Chapter 6
    Pushdown Automata : v1 v2 v3
    16
    2016-11-16
    A
    Rewriting systems for PDA's and FA's : v1 v2 v3
    15
    2016-11-16
    B
    Deterministic Left Parsers : v1 v2 v3 v4
    11
    2016-11-25
    C
    Deterministic Right Parsers : v1 v2 v3 v4 v5
    6
    2016-12-02
    Chapter 7
    Properties of context-free Languages : v1 v2
    24
    2016-11-09
    1
    Guarded Commands, Nondeterminancy, and Formal Derivation of Programs : v1 v2
    8
    2016-11-11
    Part IV
    Chapter 8
    Introduction to Turing Machine : v1 v2 v3
    14
    2016-12-07
    Chapter 9
    Undecidability : v1 v2
    21
    2016-12-07
    1
    Theory of Computation : v1
    46
    2016-11-30
    2
    Partial Recursive Functions : v1
    34
    2016-11-30
    Chapter 10
    Introduction to Problems : v1 v2
    20
    2016-12-07
    1
    NP complete 문제는 수학인가 : v1
    8
    2016-12-07
    Paper
    Guarded Commands, Nondeterminancy, and Formal Derivation of Pddrograms : v1
    5
    2016-11-04
    Chapter X
    2012 SIGPL 겨울학교 : v1
    62
    2016-11-16
    62

  • 한글 강의 노트 ( cf. 2016 CS322 Homepage)
    파트 챕터 섹션 제목 PDF 쪽수 최종수정일
    목차
    0
    한글 강의 노트 목차 : v1
    v1
    1
    2016-09-02
    Part I
    Chapter 1
    1
    강의개요 : v1
    v1
    4
    2016-08-31
    2
    수학기초 : v1
    v1
    6
    2016-08-31
    3
    증명 : v1
    v1
    7
    2016-08-31
    4
    Recursion 혹은 수학적 귀납법과 무한집합 : v1
    v1
    4
    2016-08-31
    5
    언어이론(Language Theory) 기초 : v1
    v1
    3
    2016-08-31
    Part II
    Chapter 2
    1
    Deterministic Finite Automata : v1
    v1
    4
    2016-09-14
    2
    DFA의 확장(1) : v1
    v1
    4
    2016-09-14
    3
    DFA의 확장(2) : v1
    v1
    4
    2016-09-14
    4
    한글 모아쓰기 오토마타와 Output Machine : v1
    v1
    3
    2016-09-14
    Chapter 3
    1
    Regular Expression : v1
    v1
    1
    2016-09-22
    2
    FA to RE(보충) : v1
    v1
    3
    2016-09-22
    Chapter 4
    1
    정규언어를 위한 pumping lemma : v1
    v1
    4
    2016-09-29
    2
    정규언어에 닿혀있는 성질 : v1
    v1
    3
    2016-09-29
    3
    Myhill-Nerode Theorem : v1
    v1
    3
    2016-09-29
    Part III
    Chapter 5
    1
    문맥자유문법과 정규문법 : v1
    v1
    3
    2016-10-12
    2
    문맥자유문법의 문법나무와 유도순서 : v1
    v1
    3
    2016-10-12
    Chapter 6
    1
    Pushdown Automata : v1
    v1
    3
    2016-11-16
    2
    문맥자유문법(CFG)와 왼 파서(Left Parser) : v1
    v1
    3
    2016-11-16
    Chapter 7
    1
    쓸모 있게(Useful) 줄인 문법(Reduced Grammar) : v1
    v1
    3
    2016-11-16
    2
    Chomsky Normal Form : v1
    v1
    4
    2016-11-16
    3
    Loop Invariance and Termination(보충) : v1
    v1
    3
    2016-11-16
    4
    Context-Free 언어를 위한 Pumping Lemma : v1
    v1
    3
    2016-11-16
    5
    CYK 알고리즘 : v1
    v1
    2
    2016-11-16
    Part IV
    Chapter 8
    1
    Turing Machine과 Chomsky의 언어(문제) 계급 : v1
    v1
    1
    2016-12-02
    Chapter 9
    1
    Undecidability : v1
    v1
    3
    2016-12-02
    2
    Primitive Recursive Function : v1
    v1
    3
    2016-12-02
    3
    mu-Recursive Partial Function : v1
    v1
    3
    1970-01-01
    Chapter 10
    1
    NP-completeness : v1
    v1
    3
    1970-01-01
    2
    Satisfiability Problem : v1
    v1
    2
    2016-12-02
    26
  • 숙 제
    • Homework
      • 공 지
        숙제는 일주일에 한 번씩, 매주 목요일(에 홈페이지에 공지될 예정입니다.
      • 마감
        공지한 다음 주 수요일 오후 11:59까지 입니다.
      • Delay
        Due 이후에 제출된 숙제는 일체 받지 않습니다.
      • 제출 방식
        제출 장소는 N1 403호 앞 숙제함입니다.
      • 숙제 Return
        숙제 Due에서 2주 후 월요일 숙제함 근처에 채점된 숙제를 모아 놓을 테니 찾아가시면 됩니다.
  • 필기숙제
    출제일 제출일 숙제 풀이 담당조교
    -
    2016/09/22(목)
    이정준
    2016/09/21
    2016/09/29(목)
    고병수
    2016/09/28
    2016/10/6(목)
    곽진명
    2016/10/07
    2016/10/14(금)
    손명배
    2016/10/13
    2016/10/13(목)
    정경준

  • 프로젝트
    출제일 제출일 프로젝트 HWP PDF 출제자 채점 기준 담당조교
    2016/09/13
    2016/09/28
    1. 예비 1-1
    HWP
    PDF
    최광무
    고병수
    2016/09/21
    2016/10/05
    2. 예비 1-2
    HWP
    PDF
    최광무
    이정준
    2016/09/28
    2016/10/19
    3. 프로젝트 1
    HWP
    PDF
    최광무
    김성훈,정경준,정진근
    2016/10/12
    2016/11/09
    4. 예비 2-1
    HWP
    PDF
    최광무
    윤정필, 곽진명
    2016/11/03
    2016/11/23
    5. 프로젝트 2
    HWP
    PDF
    최광무
    손명배
    2016/11/17
    2016/12/14
    6. 프로젝트 3_rev
    HWP
    PDF
    최광무
    김성훈,정경준,정진근
    • 사용가능한 프로그래밍 언어는 C/C++/Python/Java 입니다. 이외의 언어를 사용하셔도 되지만, 조교들이 해당 언어에 능숙하지 않아서 발생하는 불이익이 있을 수 있습니다.
    • 제출물: 소스코드 (라이브러리 포함), 실행가능파일, 간단한 메뉴얼(실행법(입/출력 예시), 프로그램 설명, 실행 결과 스크린샷 포함)
    • 제출 방법: 모든 제출물을 [프로젝트이름].zip으로 압축하여 KLMS로 제출 바랍니다.(Google 메일에서 실행파일을 받을 수 없는 문제가 발생하여 부득이하게 방법을 바꾸게 되었습니다.) ex) [예비프로젝트1-1].zip


  • 프로젝트 참고자료
    등록일 파일 이름 제목
    2012/10/20
    Lex & Yacc의 소개 및 사용법
  • 조 교 정 보
    • 조교 Office Hour: ?

    이 름 연 구 실 이 메 일 담 당
    손명배
    E3 3432
    nedsociety@kaist.ac.kr
    조교장
    이정준
    E3 2422
    j2in2o@kaist.ac.kr
    숙제
    김성훈
    E3 2422
    shkim0604@kaist.ac.kr
    웹, 숙제
    곽진명
    E3 2422
    kwak.jinmyung@kaist.ac.kr
    출석, 숙제
    고병수
    -
    -
    출석
    윤정필
    -
    jdsp@nclab.kaist.ac.kr
    숙제
    정경준
    -
    -
    숙제
    정진근
    -
    -
    숙제
    조교이름
    연구실 위치
    이메일
    담당 역할

    출 석
    • KMLS에 올라온 사진을 보고 출석 구글폼 링크에 들어가 출석 체크를 해 주십시오. 되도록이면 빨리 해 주시면 좋겠습니다.
    • 3번 결석 까지는 봐주지만, 그 이상 결석하면 점수에 영향을 주게 됩니다.

    부교재 Martin책의 TP
    Chapter 제목 쪽수
    Chapter 1
    Mathematical Tools and Techniques
    56
    Chapter 2
    Finite Automata and the Languages They Accept
    42
    Chapter 3
    Regular Expressions, Nondeterminism, and Kleene’s Theorem
    25
    Chapter 4
    Context-Free Languages
    31
    Chapter 5
    Pushdown Automata
    39
    Chapter 6
    Context-Free and Non-Context-Free Languages
    23
    Chapter 7
    Turing Machine
    42
    Chapter 8
    Recursively Enumerable Languages
    35
    Chapter 9
    Undecidable Problem
    30
    Chapter 10
    Computable Functions
    42
    Chapter 11
    Introduction to Computational Complexity
    27

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