Discrete Math II Howon Kim 2018.10.

Slides:



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

게임이론 Von Neumann Theory of Games and Economic Behavior with Oskar Morgenstern, widely recognized as the first formal treatment.
1 As protons are added one by one to the nucleus to build up the elements, electrons are similarly added to these hydrogen-like orbitals. As protons are.
언어와 문법 (languages, grammar)
컴파일러 입문 제 5 장 Context-Free 문법.
Master Thesis Progress
Chapter 9. 컴퓨터설계기초 9-1 머리말 9-2 데이터 처리장치 (Datapath)
Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems.
Compiler Lecture Note, Inroduction to FL theory
소프트웨어란?.
Chapter 1 1. Turing proposed in 1937 that all computations could be carried out by a particular kind of machine, which is now called (a Turing machine).
DS020 오토마타형식언어 Chapter 3. Regular Languages and Regular Grammars
Chapter 7 ARP and RARP.
Compiler Lecture Note, Inroduction to FL theory
Chaper 2 ~ chaper 3 허승현 제어시스템 설계.
Digital Logic Structures
Discrete Math II Howon Kim
기본 컴퓨터 프로그래밍 Lecture #6.
Computer System Architecture
Sequential logic circuit
순차로직 개요.
4장 구문(Syntax).
강좌 개요 2009년 1학기 컴퓨터의 개념 및 실습.
과목 홈페이지  전산학개론 이메일 숙제를 제출할 경우, 메일 제목은 반드시 ‘[전산학개론]’으로 시작.
REINFORCEMENT LEARNING
< 생산자동화 기능사 실기수준 >
Discrete Math II Howon Kim
2. 형식언어 (Formal Language)
Computer System Architecture
오토메타 형식언어 2003년도 제 2학기.
제 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
Discrete Math II Howon Kim
FSM 설계.
주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합.
발표자 : 홍익대학교 소프트웨어 공학 연구실 변은영 지도교수 : 김영철
계수와 응용 (Counting and Its Applications)
Chapter 4 The Von Neumann Model.
학습목표 CFL을 accept하는 오토메타인 pda를 이해 npda와 dpda의 차이를 compiler의 측면에서 학습
제 4 장. Regular Language의 특성
학습목표 Pumping Lemma와 Closure 특성을 통해 CFL와 Language Family간의 관계 이해
Sequence Logic.
강의 소개, 자료구조의 개념, SW 개발과 자료구조
Discrete Math II Howon Kim
Introduction to Programming Language
Discrete Math II Howon Kim
소프트웨어 공학 (Software Engineering) 요구 분석 (Requirement Analysis)
관계 기본 개념 관계의 표현 관계의 성질 관계의 연산 관계의 폐포 동치 관계 부분순서 관계.
3. 정규 언어(Regular Language)
Chapter 12 Memory Organization
4. 어휘 분석(Lexical analysis)
Chapter 5. Context-Free Language Exercises
이산수학(Discrete Mathematics)
Internet Computing KUT Youn-Hee Han
제12장. Algorithmic Computation의 한계
4. Flip-Flops : S-R, D, J-K, T 컴퓨터 구조 실습 안내서.
점화와 응용 (Recurrence and Its Applications)
Chapter 09. 동기 순서논리회로.
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics) 수열과 합 (Sequences and Summations)
제 3장. Regular Languages 와 Regular Grammars
제10장. Other Models of TM’s 학습목표
[CPA340] Algorithms and Practice Youn-Hee Han
Chapter 7: Deadlocks.
Presentation transcript:

Discrete Math II Howon Kim 2018.10

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

Finite State Machine Finite State Machines (FSM) It consists of a finite number of internal states and transitions among them. It remembers certain information when it is in a particular state. Coin Checker Change Maker Coffee Reset Reject

DFA(Deterministic Finite Automata) Definition A deterministic finite automata(DFA) M is specified by a quintuple M = (Q, ∑, , q0, F) where Q is an alphabet of state symbols ; ∑ is an alphabet of input symbols ;  : Q x ∑  Q is a transition function ; q0  Q is the start state; and F  Q is a set of final states. Deterministic : there is one and only one transition to a next state !

Machine-oriented Viewpoint Let M = (Q, ∑, , q0, F) be a DFA. We view it as a machine (a primitive computer) It has an input tape of cells, a read-only head, and a finite control Input tape  No memory  Read-only head  Move the head to the right  Initially at the start state & at the leftmost position   (current state, tape symbol)  (next state) Finite Control 1 Reading head M = (Q, ∑, , q0, F)

DFA Example M = (Q, ∑, , q0, F) Q = { 0, 1, 2 } , ∑ = { a }  : Q x ∑  Q  (0,a) = 1,  (1,a) = 2,  (2,a) = 0 q0 = 0 , F = { 2 } State Diagram start accept a 1 2

DFA Configuration Definition Let M = (Q, ∑, , S, F) be a DFA. We say that a word in Q∑* is a configuration of M. It presents the current state of M and the remaining unread input of M. That is, configuration : what state the DFA is currently in, and what ‘input’ is left to process ! Let px and qy are two configurations of a DFA M. We write px┣ qy, if x = ay for some a  ∑ and  (p,a) = q. a p q x y 혹은 (p,x) ┣ (q,y)로 표현 가능: “configuration (p,x) yields configuration (q,y)”

Configuration Sequence Definition For k  1, we write px┣k qy (k-steps of M on px), if 1) k = 1 and px┣ qy or 2) k > 1 and there exists a configuration rz such that px┣ rz and rz┣k-1 qy. x p q r z … y k-1 transitions State p에서 sequence x…에 의해, state qy로 가도록 하는 것을 configuration sequence라고 함. 여기서 qy에서 y가 lambda (empty string) 이라면, q가 됨.

Configuration Sequence ┣ : a binary relation on Q∑* ┣+ : transitive closure of┣ (px┣+ qy) ┣* : reflexive, transitive closure of┣ (px┣* qy) We say that the sequence of configuration given by px┣* qy is a configuration sequence. Final state은 결국 q0로 감 q0 1010 ┣ q1 010 q0 1010 ┣+ q1 10 q0 1010 ┣* q0  q0  ┣* q0  1 q0 q1 q1에서 one or more move q0에서 zero or more move Q0에서 1010 sequence에 의해, q0가 됨. 이 관계는 q1에서 010 moves와 동일함. |- * : zero or more moves를 의미함. |- + : one or more moves? ┣* : zero or more moves ┣+ : one or more moves reflexive : for all x in X it holds that xRx. (예: “=“) transitive : for all x, y and z in X it holds that if xRy and yRz then xRz.

Accepted Language Definition Let M = (Q, ∑, , S, F) be a DFA. We say that a string x in ∑* is accepted by M, if Sx┣* f  , for some f in F. We say that Sx┣* f  is an accepting configuration sequence. The set of words accepted by M, called the language accepted, defined, or recognized by M is denoted by L(M) and is defined as L(M) = {x|x  ∑* and Sx┣* f, for some f in F }. Starting 상태 S에서 입력 string x에 의해, final 상태 f로 됨.. 그런, x가 존재할 때, accepted 되었다고 함. f (lambda) 상태는 f 상태임 Sx yields f

DFA Language DFA Language Equivalence of DFAs That is, deterministic finite automata (DFA) is also known as a deterministic finite acceptor (DFA) ! DFA Language The notion of acceptance has caused a DFA to stand for deterministic finite acceptor (결정적 유한 인식기). We say that L  ∑* is a DFA language if there is a DFA M, with L = L(M). Equivalence of DFAs Let M1 and M2 be two DFAs. If L(M1) = L(M2), we say that M1, M2 are equivalent.

State Diagram State Diagram of M = (Q, ∑, , q0, F) state symbols in Q ; vertices (원) input symbols in ∑ ; labels  : Q x ∑  Q : edges with labels (화살표) q0  Q : start로 명시된 vertex (구별되는 화살표) F  Q : 이중 원 1 q0 q1 What is the L(M) ? 1이 짝수개인 스트링의 집합

How to construct DFAs DFA는 다음 두 단계로 만든다 주의할 점 1. 현재 까지 읽은 부분에서 어떤 정보를 기억해야 하는지를 정하고 이 정보를 state로 표시한다. 2. 새로운 input symbol을 읽었을 때 기억해야 하는 정보가 어떻게 바뀌는지를 보고 transition function 을 만든다. 주의할 점 중요한 것은 기억해야 하는 정보를 정하는 것이다. 만들고자 하는 DFA의 기능을 분석하여 기억해야 하는 정보를 정리하고 state로 매핑한다.

Example (1) 1이 짝수개인 string을 accept하는 DFA를 구하라. 현재까지 읽은 substring에서 1의 개수에 대한 짝수 또는 홀수 여부를 상태로 기억해야 함. 1 q0 q1

Example (2) 0101을 substring으로 가지는 string을 accept 하는 DFA를 구하라. 0101의 prefix중에서 현재까지 read한 부분을 기억해야 함. 따라서, 0101의 prefix에 해당하는 state를 만들면 됨. 1 start accept A E D C B 0,1 Final state

Example (3) 0101을 substring으로 갖지 않는 string을 accept하는 DFA를 구하라. 앞 예제에서의 final state와 그 외의 상태를 맞바꾸면 됨. 1 start A E D C B 0,1 Dead State 한번 들어가면 빠져 나오지 못하는 상태(it is not an accepting state and has no out-going transitions except to itself)

Another Example of Dead States (010+01)* string을 accept하는 DFA? 1 1 S0 S1 S2 S3 1 0,1 SD

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

A Modified FA for Logic Design Def. Modified FA M = ( Q, , , ,  ) Q : a set of finite states  : an input alphabet  : an output alphabet  : next state function Q    Q  : an output function Q     (note) DFA M = ( Q , ∑ ,  , q0 , F )

An Example of the M-FA (010+01)+ string을 accept하는 DFA? S0 S1 S3 S4 S2 Original DFA S0 S1 S2 S3 SD input output M = ( {S0,…,S4}, {0,1}, {0,1}, ,  ) M = ( Q, , , ,  )

continue (010+01)+ string을 accept하는 DFA? S1 S2 S3 S4 S0 S1 S4 0 1 0 0 0 1 0 0 1 0 S4 S2 S3 S4 S1 S2 S4 S4 (next state fn) (output fn.) S0 S1 S3 S4 S2 M = ( {S0,…,S4}, {0,1}, {0,1}, ,  ) State (Transition) Table M = ( Q, , , ,  )

continue State Assignment & F/F Excitation Table 0 0 0 1 1 0 1 1 0 x 0 0 0 1 1 0 1 1 0 x 1 x x 1 x 0 Q Q+ J K 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 A B C 1 X Y N.S. C.S. I O no chg S1 S2 S3 S4 S0 S1 S4 0 1 0 0 1 0 S4 S2 S3 S4 S1 S2 S4 S4   set reset no chg J=K=1: toggle 0 0 0 1 1 0 1 1 Q Q+ 1 D

continue Input Equations 1 x 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 A B C 1 X Y 1 X Y N.S. C.S. I O 1 x DB = CX+BC’X’ DA = A+C’X+B’CX’ 1 x DC = A’C’X’+B’CX’ x 1 O = DB

continue CP DA = A+C’X+B’CX’ DB = CX+BC’X’ DC = A’C’X’+B’CX’ O = DB AA’ BB’ CC’ XX’

continue 1 FA Controller CP AA’ BB’ CC’ XX’

Another Example (0+1)*01001을 accept하는 DFA? S0 S1 S3 S2 S4 S5

Another Example (0+1)*011101을 accept하는 DFA? S0 S1 S3 S2 S4 S5 S6