Discrete Math II Howon Kim 2018. 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