CS522 Automata and Formal Languages Theory

2015년 봄학기

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


이전 홈페이지

2013 2014


시험 공지

l  중간고사: 2015.4.21. 화요일 13:00 ~ 14:30

l  기말고사: 2015.6.16. 화요일 13:00 ~ 14:30


프로젝트 공지

l  Project #1:
RE를 읽어서 AST(Abstract Syntax Tree) generate 하는 프로그램을 쓰시오.

l  Specification:
1. Lex
Yacc 외 유사한 소프트웨어 이용.(Java의 경우 CUP 등을 이용)
2. LL Parsing(Top-down)
은 안되고 반드시 LR Parsing(혹은 bottom-up)만 사용할 것.

l  Due:
4/9(
, 10일 되기 전)까지 제출
제출: kaist.cs522@gmail.com

 

l  Project #2:
Regular ExpressionAST를 보고 minimal state DFA 만들기

l  과정:
1.
Project #1에서 만든 AST를 보고 e-NFA 만들기
2.
1에서 만든 e-NFADFA로 바꾸기
3.
2에서 만든 DFA에서 equivalent state를 합쳐서 m-DFA로 만들기

l  Due:
5/17(
, 18일 되기 전)까지 제출
제출: cs522@cs.kaist.ac.kr로 압축파일 이름을 본인의 한글이름으로 보낼 것.(예: 이의현.zip, 홍길동.gz, ...) 압축은 한번만 할 것.

 

l  Project #3:
한글 모아쓰기 오토마타 만들기

l  Specification:
한글을 입력하면 모아서 한글을 만들어 주는 오토마타(Mealey Machine)을 만드시오.
단, 3x4 휴대폰 자판(서로 다른 심볼이 12개)을 가정하고, 오토마타는 lex만을(yacc 쓰지않고) 이용하여 만드시오. (state가 매우 크므로 손으로 만들기는 쉽지 않음)
또한, 초성우선종성우선 두 가지 경우에 대해서 만드시오.
초성우선: ㅎ - 하 - 하ㄹ - 할ㅁ - 할머 - 할머ㄴ - 할머니
종성우선: ㅎ - 하 - 할 - 핢 - 할머 - 할먼 - 할머니

l  Due:
6/14(
, 15일 되기 전)까지 제출
제출: cs522@cs.kaist.ac.kr로 압축파일 이름을 본인의 한글이름으로 보낼 것.(예: 이의현.zip, 홍길동.gz, ...) 압축은 한번만 할 것.


연습 문제

  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/03

1 강의

Set Isomorphism & String Over V

03/10

2 강의

Uncountable & 불행한 수학자들

03/12

3 강의

Rewriting System

03/17

4 강의

Regular Expression

03/19

5 강의

Finite Automata

03/24

6 강의

FA Regular Grammar

03/26

7 강의

FA(or RG) to RE

03/31

8 강의

Context-Free Language

04/02

9 강의

SIGPL 겨울학교

04/07

10 강의

CFL-useful & nullable

04/09

11 강의

Parser

04/14

12 강의

SLL(1) Grammar

04/16

13 강의

Left & Right Parsers

04/28

14 강의

Shift & Reduce Parser

04/30

15 강의

Viable Prefix = Viable Stack String

05/07

16 강의

Viable Prefix is a Viable Stack String

05/12

17 강의

Canonical Collection of LR(k) States

05/14

18 강의

SIGPL 겨울학교

05/19

SIGPL 겨울학교

05/21

Valid LR(k) Items

05/26

21 강의

LR(k) & LL(k) Parsing

06/02

22 강의

LL(k) Parsing

06/04

23 강의

Godel's Incompleteness Theorem

06/09

24 강의


교과서 TP

l  Table of Contents

l  Chapter 1. Elements of Language Theory

l  Chapter 3. Regular Languages

l  Chapter 4. Context-free Languages

l  Chapter 5. Parsing

n  Strong LL(k) Parsing

l  Chapter 6. LR(k) Parsing

l  Chapter 8. LL(k) Parsing


SIGPL2012 겨울학교(Winter School)

l  2012 겨울학교

l  책갈피


Lex, Yacc & NP-complete

l  lex_yacc_1

l  lex_yacc_2

l  NP_complete

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