CS522 Automata and Formal Languages Theory

2014년 봄학기

본 강의는 모국어로 이루어진다.


조교

l  이름: 오교중 Office Hour: Tue/Thu PM 2:30 ~ 4:00 (E3-1 #2112, N1 #724)

l  연락처: aomaru at kaist.ac.kr


시험 공지

l  중간고사: 2014.4.22. 화요일 13:00 ~ 15:45

l  기말고사: 2014.6.17. 화요일 13:00 ~ 15:45


프로젝트 공지

l  Project #1:

RE를 읽어서 minimum state DFA generate 하는 프로그램을 쓰시오.

 

l  Specification:
1. Lex
Yacc 외 유사한 소프트웨어 이용.(Java의 경우 CUP 등을 이용)
2. LL Parsing(Top-down)
은 안되고 반드시 LR Parsing(혹은 bottom-up)만 사용할 것.
3.
구현 과정: RE AST → ε-NFA DFA mDFA.
(*
각 과정의 중간 수행 결과를 출력해 주시면 채점하기가 편해집니다.)
4.
ε 또는 concatenation 중 한 쪽만 이용하여 구현해 주세요.

l  Due:
4/30(
, 1일 되기 전)까지 제출, 5 1() 강의 시간에 개인당 5분씩 발표.
(*
데모용 노트북 및 컴퓨터 환경 필요하신 학생들은 연락 주시기 바랍니다.)
수정 또는 추가된 사항이 있으면 다시 제출해 주시기 바랍니다.

 

l  Project #2 :

문법이 주어 졌을때 LL(1) Analysis를 하고 parsing table을 만들어주세요.

 

l  Specification:
1.
주어진 문법에 대한 파싱 테이블 출력
2.
수행 결과가 LL parsing인지 확인할 수 있는 결과

l  Due:
제출: 발표 전날 (6 11) 수요일 자정까지 - 연기 되었습니다. 확인 요망
발표: 수업 마지막주 (6 12) 목요일 수업 시간

 

l  공지사항

*Project ()제출은 aomaru at kaist.ac.kr ndex.oh at gmail.com으로 둘 다 해 주세요.(가끔 필터링을 당합니다. 실행파일 바이너리 포함 시)*

*파일을 잘 받았으면, 제가 수신을 보내드립니다. 안 받으신 분들은 발표 당일에 다시 제출해 주세요.*

*데모에 필요한 환경을 파일 보내실 때 알려주세요.*


연습 문제

  1. Exercise Chap 1, Exercise Chap 3, Exercise Chap 4, Exercise Chap 5
  2. Exercise Chap 6, Exercise Chap 7, Exercise Chap 8

강의 영상 및 필기

강의 주제

강의 날짜

강의 필기

강의 사진

Introduction, Relation & Function

03/04

1 강의

Relation & Graph relation

03/06

2 강의

Set isomorphism & Cordinality

03/11

3 강의

Algebraic System

03/13

4 강의

Rewriting System

03/18

5 강의

Regular language

03/20

6 강의

Regular Expression Finite Automata

03/25

7 강의

사진-AST

Finite-state Automata

03/27

8 강의

Compiler

04/01

9 강의

DFA, NFA, and ε-NFA are same!

04/03

10 강의

Pumping Lemma for Regular Languages

04/08

11 강의

Myhill-Nerode Theorem & Minimization of DFA

04/10

12 강의

Context-free languages

04/15

13 강의

Loop Invariance

04/17

14 강의

Parsing

04/29

15 강의

Left Parser & Homomorphism

05/01

16 강의

Strong LL(k)

05/13

17 강의

LL(1) Parsing

05/15

18 강의

LL(1) Example

05/20

19 강의

LR parsing 1

05/22

20 강의

LR parsing 2

05/27

21 강의

Viable prefices & LR items

06/03

23 강의

LR(k) state & Set of LR items

06/03

24 강의


교과서 TP

l  Table of Contents

l  Chapter 1. Elements of Language Theory

u  Last modified:

l  Chapter 2. Algorithms on Graph

u  Last modified:

l  Chapter 3. Regular Languages

u  Last modified:

l  Chapter 4. Context-free Languages

u  Last modified:

l  Chapter 5. Parsing

u  Last modified: 04 / 21 / 2011

n  Supplementary Material-Proof

n  Left and Right Parsers

u  Last modified: 05 / 12 / 2011

n  Strong LL(k) Parsing

u  Last modified: 04 / 28 / 2011

n  Supplementary Material-Strong LL(k)

l  Chapter 6. LR(k) Parsing

n  Supplementary Material

u  Last modified: 05 / 20 / 2011

n  Machine for expression grammar

u  Last modified:

l  Chapter 7. Construction and Implementation of LR(1) Parsers

u  Last modified:

n  Supplementary Material

u  Last modified: 05 / 20 / 2011

n  Error Recovery

u  Last modified:

l  Chapter 8. LL(k) Parsing

u  Last modified:

n  Supplementary Material

u  Last modified: 05 / 20 / 2011

n  Example LL(0)

u  Last modified:

n  Example LL(1)

u  Last modified:

n  Example LL(2)

u  Last modified:

l  Comparisons on LR(k) and LL(k) Parsings

u  Last modified:

l  Chapter 9. Syntax Error Handling

u  Last modified:

n  Insert only Error Recovery

u  Last modified:

l  Chapter 10. Testing Grammars for Parsability

u  Last modified:


SIGPL2012 겨울학교(Winter School)

l  2012 겨울학교

l  책갈피


Lex, Yacc & NP-complete

l  lex_yacc_1

l  lex_yacc_2

l  NP_complete

l  아래한글_오토마타(Mealy Machine)