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