Presentation is loading. Please wait.

Presentation is loading. Please wait.

Discrete Math II Howon Kim 2018. 11.

Similar presentations


Presentation on theme: "Discrete Math II Howon Kim 2018. 11."— Presentation transcript:

1 Discrete Math II Howon Kim

2 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

3 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

4 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

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

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

7 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

8 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

9 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

10 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

11 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

12 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

13 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

14 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

15 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

16 Summary of Conversions
Finite Automata NFA DFA RG RE 16


Download ppt "Discrete Math II Howon Kim 2018. 11."

Similar presentations


Ads by Google