Discrete Math II Howon Kim 2017. 11.

Slides:



Advertisements
Similar presentations
CHAPTER 5 TOP-DOWN PARSING SUNG-DONG KIM, DEPT. OF COMPUTER ENGINEERING, HANSUNG UNIVERSITY.
Advertisements

Lesson 11 What’s Your Type? 여러분의 유형은 무엇인가요 ?. What job do you want to have in the future? 여러분은 미래에 어떤 직업을 갖고 싶은가 ? p.218.
언어와 문법 (languages, grammar)
컴파일러 입문 제 5 장 Context-Free 문법.
Master Thesis Progress
Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems.
Discrete Mathematics Express
Compiler Lecture Note, Inroduction to FL theory
Sources of the Magnetic Field
DS020 오토마타형식언어 Chapter 3. Regular Languages and Regular Grammars
Compiler Lecture Note, Inroduction to FL theory
Chaper 2 ~ chaper 3 허승현 제어시스템 설계.
변화관리의 출발.
Discrete Math II Howon Kim
4장 구문(Syntax).
강좌 개요 2009년 1학기 컴퓨터의 개념 및 실습.
방송통신대학교 중국어 문법의 이해 제 1장 제2장.
과목 홈페이지  전산학개론 이메일 숙제를 제출할 경우, 메일 제목은 반드시 ‘[전산학개론]’으로 시작.
REINFORCEMENT LEARNING
Discrete Math II Howon Kim
2. 형식언어 (Formal Language)
오토메타 형식언어 2003년도 제 2학기.
3장 (2) 구문과 의미론 순천향대학교 컴퓨터공학과 하상호.
Christopher G. Langton (1989) 인지과학 협동과정 강 소 영
DS020 오토마타형식언어 Chapter 6. Simplification of Context-Free Grammars and Normal Forms Exercises October 16, 2003.
푸시다운 오토마타.
제 5장. Context-Free Languages
이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)
학습목표 Turing Machine의 작동원리와 일반적인 계산모형으로서의 가능성 이해
Tel : Office : 2공학관 408호 오토마타 및 형식언어 김 현 성 Tel : Office : 2공학관 408호
Sung-Hae Jun 자연어 처리의 이해 Sung-Hae Jun
Chapter 7. PUSHDOWN AUTOMATA Exercises
학습목표 가장 단순한 Finite Automata를 통해 DFA와 NFA를 이해하고 그 둘의 능력이 같음을 확인한다.
Chapter 2. Finite Automata Exercises
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합.
계수와 응용 (Counting and Its Applications)
2. 형식언어 (Formal Language)
학습목표 CFL을 accept하는 오토메타인 pda를 이해 npda와 dpda의 차이를 compiler의 측면에서 학습
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
제 4 장. Regular Language의 특성
학습목표 Pumping Lemma와 Closure 특성을 통해 CFL와 Language Family간의 관계 이해
adopted from KNK C Programming : A Modern Approach
과학 탐구 토론 대회 1학년 2반 박승원 1학년 5반 권민성.
우리는 부모를 닮지만, 왜 똑같지는 않을까? 유전적 다양성 독립 연관과 교차 무작위 수정.
Discrete Math II Howon Kim
Introduction to Programming Language
Discrete Math II Howon Kim
문제 다음의 서술적 언어로 표현된 요구사항을 DFD로 완성하시오
3. 정규 언어(Regular Language)
CEO가 가져야 할 품질 혁신 마인드.
Discrete Math II Howon Kim
4. 어휘 분석(Lexical analysis)
Chapter 5. Context-Free Language Exercises
이산수학(Discrete Mathematics)
제12장. Algorithmic Computation의 한계
점화와 응용 (Recurrence and Its Applications)
제 6 장  상향식 파싱.
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
이산수학(Discrete Mathematics)
진리 나무 Truth-tree  ∧ ∨ → ↔  =.
수학 8나 대한 64쪽 II.도형의 성질 2. 사각형의 성질 §1. 평행사변형 (17/24) 평행사변형이 되는 조건.
노동조합 활동 사례 희망연대노동조합.
이산수학(Discrete Mathematics) 수열과 합 (Sequences and Summations)
제 3장. Regular Languages 와 Regular Grammars
제10장. Other Models of TM’s 학습목표
[CPA340] Algorithms and Practice Youn-Hee Han
우리나라에서 10대로 살아가기 엘리트조 오정희 / 송지선 / 손시하 / 박주현 / 김소현.
표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =.
시나브로 기획안.2 By.임나연.
Presentation transcript:

Discrete Math II Howon Kim 2017. 11

Agenda 1 Automata Theory 2 Regular Expression & Regular Languages 3 Finite Automata DFA(Deterministic Finite Automata) FA Applications 4 Non-deterministic Finite Automata 5 Grammars & Languages 6 Theory of Computations

Overview Set Theory of Strings (Chapter 6.1) Regular Expressions & Regular Languages Finite State Machines Deterministic Finite Automata (DFA) Non-deterministic Finite Automata (NFA) Grammars and Languages Types of Grammars and Languages Associated Machines including Turing Machine Computation Theory NP Problem

Regular expression & NFA DFA에 의해 인식되는 language  regular language DFA와 NFA는 equivalent하므로, NFA에 의해 인식되는 language도 regular language가 됨 Regular expression을 표현하는 automata ?  를 인식하는 NFA 를 인식하는 NFA a  ∑를 인식하는 NFA Automata를 대략적으로 기술함 L(r)을 인식하는 NFA의 도식적 표현 방법 초기상태 Accept 상태 4

Regular expression & NFA L(r1+r2)를 위한 NFA L(r1*)를 위한 NFA L(r1r2)를 위한 NFA 5

Regular expression & NFA L(a+bb)를 위한(인식하는) NFA 오토마타 L(ba*+ )를 위한(인식하는) NFA 오토마타 L((a+bb)*(ba*+ )를 위한(인식하는) NFA 오토마타 6

Regular Grammar Regular language is also described by using the grammars That is, grammars are often alternative way of specifying languages Regular grammar is either a right linear or left linear Right linear grammars (우선형 문법) Left linear grammars (좌선형 문법) 변수는 하나만 올 수 있음 G = ( V, , S, P ) V : a finite set of variables  : an alphabet S : a start variable, S  V P : a set of production rules (생성규칙) 7

Regular Grammar Example) The grammar G1=({S},{a,b},S,P1), with P1 given as S abS | a Right linear grammar SabS  ababS  ababa … G = ( V, , S, P ) V : a finite set of variables  : an alphabet S : a start variable, S  V P : a set of production rules 8

Def. of Grammar Definition of grammar(문법) G = ( V, , S, P ) V : a finite set of variables  : an alphabet S : a start variable, S  V P : a set of production rules Production rule : x  y where x  (V  )* V (V  )* and y  (V  )* A,BV, a,b  A  aB |  aB  aAb A  aB A   r과 s가 정규식이라면, r|s도 정규식 (r or s) 9

Regular Grammar Construct a finite automaton that accepts the language generated by the grammar V0 aV1, V1 abV0|b V0, V1, Vf를 갖는 transition graph를 구성함 첫번째 생성 규칙에의해 V0와 V1사이에 라벨 a인 간선을 생성함 두번째 생성 규칙에 의해 오토마타에 새로운 정점 하나 추가하고 V1과 V0 사이에 라벨 ab인 경 로가 존재하도록 함 마지막으로 V1과 Vf 사이에 라벨 b인 간선 추가 이 문법에 의해 생성되고 또한 오토마타에 의해 인식되는 언어는 정규 언어 L ((aab)*ab) V0 aV1  ab  10

Language of a Grammar Def. Language of a grammar For a grammar G = (V,,S,P), the language being derived from the G is defined as L(G) = { w  * | S * w } ,where * indicates the k-times derivation (k0). The derivation is the process of applying a production rule to x  (V  )* V (V  )*. A  aB |  aB  aAb A  aB  aAb  aaBb  aaAbb  aabb 11

Regular Grammar Def. of Regular Grammar G = ( V, , S, P ) where all the production rules have the form A  wB or A  w, A,B  V and w  *. The language L(G) being derived from a regular grammar G is called a regular language. 12

An Example (Ex.) Find the regular language that is derived from the following regular grammar. G = ( {S,A}, {a,b}, S, P ) P : S  aA A  abS | a L(G) = { (a2b)*a2 } S aA aabS aabaA aabaabS (a2b)2aA (a2b)2aa 13

Regular Grammar  NFA (Ex.) Find a NFA that is equivalent to the regular grammar G = ( {S,A}, {a,b}, S, P ) P : S  aA A  abS | a L(G) = { (a2b)*a2 } S A F B M=({S,A,B,F},{a,b},,S,{F}) 14

DFA  Regular Grammar (Ex.) Find a regular grammar that is equivalent to the following DFA. q1 q2 q3 q4 G=({q1,q2,q3,q4},{0,1},q1,P) P : q1  0q2 |  q2  1q3 q3  0q4 |  q4  0q2 | 1q3 |  We don’t have to consider dead states that are not final states. 15

Summary of Conversions Finite Automata NFA DFA RG RE 16