오토메타 형식언어 2003년도 제 2학기

강의진 소개 담당 교수 조성배 (공대 C515;  2123-2720; sbcho@cs.yonsei.ac.kr) 웹 페이지 : http://sclab.yonsei.ac.kr/Courses/03Automata 강의 시간(장소) : 월 4, 5 목 5 (C040) 면담 시간 : 월 7, 8 실습시간 : 금 11 (A222, A417, A505, A542) 담당 조교 박찬호(cpark@sclab.yonsei.ac.kr) : 4803 김경민(kminkim@sclab.yonsei.ac.kr) : 3877 구자민(icicle@sclab.yonsei.ac.kr) 유시호(bonanza@candy.yonsei.ac.kr) 민현정(solusea@sclab.yonsei.ac.kr)

데이터 프로그램 알고리즘 데이터 구조 화일처리 데이터베이스 프로그래밍 언어구조론 소프트웨어 공학 컴파일러 컴퓨터 그래픽스 운영체제 정보통신 입문 이산구조 오토메타 형식언어 알고리즘 분석 인공지능 컴퓨터 시스템 디지털 논리회로 컴퓨터 구조 마이크로 프로세서

왜 배우나? 이 과목은 컴퓨터과학의 바탕이 되는 기본 개념들(fundamentals of computing)을 가르쳐 준다. 이들 기본 개념을 이해함으로 말미암아 다양한 software system 과 hardware system 및 이와 관련된 문제들을 이해할 수 있는 안목 (perspective)을 갖출 수 있으며, 이러한 안목은 문제를 해결하기 위한 새로운 방안을 효율적으로 찾을 수 있게 하고, 컴퓨터과학을 하나의 학문으로 바라볼 수 있게 하여 관련 지식의 응용능력과 흥미를 높인다.

Generation: Grammars) Recognition: Machines) 뭘 배우나? G M aaba acba . . . . 언어 발생 모델: 문법 (Models of Language Generation: Grammars) 언어 인식 모델:계산기 Recognition: Machines)

Recursively enumerable 구체적으로 뭘 배우나? Automata Formal Language Grammar 계산이론 Finite automata Regular language Chomsky Hierarchy Regular grammar Pushdown automata Context free language Context free grammar Linear bounded automata Context sensitive language Turing machine Recursively enumerable Unrestricted grammar

진짜로 뭘 배우나? Computer Science  Practical discipline Theory  Concepts & Principles Applications (digital design, PL, Compiler, OS, PR, AI, …) Fun Abstract model with simple notations o Alphabet o Strings : finite sequence of symbols from alphabet o Language : a subset of alphabet set

어디에 쓰이는 물건인고? R 2 1 1/ 0 0/ 0 0/ 1 0/ - (a) 회로이론(switching circuits): state diagram Running Blocked Ready block wakeup dispatch timer run out (b) 운영체제(operating systems) : process state transition (c) Web browsing: pattern matching for “cup” [c] [cu] [cup] c u p any not (c or p) not (c or u) start not(c) stmt if expr then E1 else E2 S1 S2 (d) Compiler: constructing a parse tree

뭘로 배우나? 주교재 P. Linz, An Introduction to Formal Languages and Automata (3rd Ed), Jones and Bartlett Publishers, 2001 P. Linz, An Introduction to Formal Languages and Automata (2nd Ed), D.C. Heath and Company, 1996 참고 서적 J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979 J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd Ed, Addison Wesley, 2001 D.Z. Du and K.I. Ko, Problem Solving in Automata, Languages, and Complexity, Wiley Inter-Science, 2001

어떤 순서로 배우나? 1. 9/1, 4 : 사전준비(1장) 2. 9/8 : Finite Automata (2장) 3. 9/15, 18 : Regular Languages & Grammars (3장), Program-1 4. 9/22, 25 : 정규언어의 특성(4장) 5. 9/29 : 1차 시험 6. 10/6, 9 : Context Free Languages (5장), Program-2 7. 10/13, 15 : Context Free 문법의 변환(6장) 8. 10/20~25 : 중간시험 기간 9. 10/27, 30 : Pushdown 오토메타(7장) 10. 11/3, 6 : Context Free 언어의 특성(8장) 11. 11/10 : 2차 시험, Program-3 12. 11/17, 20 : Turing Machines (9장) 13. 11/24, 27 : TM의 다양한 모델(10장), 정규언어 총정리(11장) 14. 12/1, 4 : 계산이론 소개(12장, 13장) 15. 12/8 : 3차 시험 16. 12/15~20 : 기말시험 기간

평가는 어떻게 하나? 시험 : 60% (20% * 3회) 프로그래밍 과제 : 25% (3회) 수업참여 : 15% 시험 : 60% (20% * 3회) 프로그래밍 과제 : 25% (3회) 수업참여 : 15% 출석 및 수업 참여 연습 및 실습 참여

마지막 잔소리 1. 이 과목 사전에 휴강이란 없다. 2. 컨닝하다 걸리면 끝장이다. 3. 모든 마감일에 예외란 없다.