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

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

    부교재
    부교재 3번을 9월 5일부터 9월 12일 일주일간 올리겠습니다.
    • Problem solving in automata, language, and complexity

    시 험

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

  • 강의 필기
    강의순서 강의일 파트 챕터 제목
    제 1강
    2017-08-29(화)
    Part I
    Chapter 0
    제 2강
    2017-08-31(목)
    Chapter 1
    제 3강
    2017-09-05(화)
    제 4강
    2017-09-07(목)
    Part II
    Chapter 2
    제 5강
    2017-09-12(화)
    제 6강
    2016-09-14(목)
    제 7강
    2016-09-19(화)

  • 교과서 TP
    파트 챕터 보조 TP 제목 쪽수 최종수정일
    Part I
    Chapter 0
    Introduction to Automata Theory, Languages, and Computation : v1 v2
    2
    2017-08-29
    Chapter 1
    Automata - The Methods and the Madness : v1 v2
    18
    2017-08-29
    1
    Reviews on Discrete Mathmatics : v1
    26
    2010-09-29
    Part II
    Chapter 2
    Finite Automata (v2: 내용 변경 없이 일부 순서만 바꾸었습니다) : v1 v2 v3
    34
    2017-09-15
    1
    FA Composition : v1
    4
    2017-09-05
    2
    FA Deterministic Finite Automata : v1
    8
    2017-09-05
    3
    FA with output : v1
    3
    2017-09-05
    4
    한글 모아쓰기 DFA : v1
    6
    2017-09-05
    Chapter 3
    Regular Expressions and Languages : v1
    17
    2017-09-14
    Chapter 4
    Properties of Regular Languages : v1
    28
    2017-09-15
    146

  • 한글 강의 노트
  • 파트 챕터 섹션 제목 PDF 쪽수 최종수정일
    Part I
    Chapter 0
    1
    한글 강의 노트 목차 : v1
    v1
    1
    2017-08-28
    Chapter 1
    1
    강의개요 : v1
    v1
    4
    2010-09-28
    2
    수학기초 : v1
    v1
    6
    2010-09-28
    3
    증명 : v1
    v1
    7
    2010-09-28
    4
    Recursion 혹은 수학적 귀납법과 무한집합 : v1
    v1
    4
    2010-09-28
    5
    언어이론(Language Theory) 기초 : v1
    v1
    3
    2010-09-28
    Part II
    Chapter 2
    1
    Deterministic Finite Automata : v1
    v1
    4
    2017-08-28
    2
    DFA의 확장(1) : v1
    v1
    4
    2017-09-05
    3
    DFA의 확장(2) : v1
    v1
    4
    2017-09-05
    4
    한글 모아쓰기 오토마타와 Output Machine : v1
    v1
    3
    2017-09-05
    Chapter 3
    1
    Regular Expression : v1
    v1
    1
    2017-09-14
    2
    FA to RE(보충) : v1
    v1
    3
    2017-09-14
    Chapter 4
    1
    정규언어를 위한 pumping lemma : v1
    v1
    4
    2017-09-15
    2
    정규언어에 닿혀있는 성질 : v1
    v1
    3
    2017-09-15
    3
    Myhill-Nerode Theorem : v1
    v1
    3
    2017-09-15
    54

  • 참고 자료
    • Dijkstra
      1. Go To Statement Considered Harmful, Communications of the ACM, 1968 (pdf)
      2. Guarded Commands, Nondeterminancy and Formal Derivation of Programs, Communications of the ACM, 1975 (pdf, ppt)
    • Lex & Yacc
      • [2012/10/20] Introduction to Lex & Yacc by Hyunik Na (pdf)
    • 대학(大學) (ppt)
    • 한글 오토마타 자료
      • 한글 모아쓰기 - 고교생 캠프 (ppt)

    숙 제
    • Homework
      • 공 지
        숙제는 일주일에 한 번씩, 매주 목요일(에 홈페이지에 공지될 예정입니다.
      • 마감
        공지한 다음 주 목요일 오후 11:59까지 입니다.
      • Delay
        Due 이후에 제출된 숙제는 일체 받지 않습니다.
      • 제출 방식
        제출 장소는 N1 403호 앞 숙제함입니다.
      • 숙제 Return
        숙제 Due에서 2주 후 월요일 숙제함 근처에 채점된 숙제를 모아 놓을 테니 찾아가시면 됩니다.
  • 필기숙제
    출제일 제출일 숙제 풀이 담당조교
    2016/09/05(화)
    2016/09/07(목)
    2016/09/07(목)
    2016/09/14(목)
    장현중
    2016/09/14(목)
    2016/09/21(목)
    장현중

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


  • 조 교 정 보
    • 조교 Office Hour: ?

    이 름 연 구 실 이 메 일 담 당
    이자룡
    E3-1 4438
    crystal00@kaist.ac.kr
    조교장
    강민철
    -
    mincheolkang@kaist.ac.kr
    숙제 및 프로젝트
    장현중
    -
    promush@kaist.ac.kr
    숙제 및 프로젝트
    배병일
    -
    bae.b.i@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