학습목표 가장 단순한 Finite Automata를 통해 DFA와 NFA를 이해하고 그 둘의 능력이 같음을 확인한다.

Presentation on theme: "학습목표 가장 단순한 Finite Automata를 통해 DFA와 NFA를 이해하고 그 둘의 능력이 같음을 확인한다."— Presentation transcript:

1 학습목표 가장 단순한 Finite Automata를 통해 DFA와 NFA를 이해하고 그 둘의 능력이 같음을 확인한다.
No temporary storage 닭머리 기계 (기억용량에 제약) CU내의 finite한 분량의 상태를 저장하여 처리

2 Generation: Grammars) Recognition: Machines)
뭘 배우나? G M aaba acba 언어 발생 모델: 문법 (Models of Language Generation: Grammars) 언어 인식 모델:계산기 Recognition: Machines)

3 개요 Deterministic Finite Accepters (DFA) DFA의 정의와 transition graph
DFA가 accept하는 언어  regular language Nondeterministic Finite Accepters (NFA) NFA의 정의와 nondeterminism의 필요성 Equivalence of DFA & NFA Reduction of Number of States in FA mark & reduce algorithm

4 Deterministic Accepters
DFA의 formal한 정의와 작동과정을 이해하자

5 DFA : Transition Graph a q1 q0 DFA를 시각적으로 쉽게 볼 수 있도록 하는 그래프 표현방법 이해
1 2 01? 00 ? - Extended transition function d* : Q x S*  Q

6 DFA : Languages DFA가 accept하는 언어의 정의와 Transition graph와의 관계 이해
L(M) = {w | M은 input string w를 모두 읽고accepting state에 들어간다} Nonacceptance? Ex 2.2 : multiply labeled edges Trap state 1 2 a b a, b  anb - Thm : M = (Q, S, d, q0, F)  GM  induction on |w| d*(qi, w) = qj iff qi  qj w - 구현 : simple table-lookup, sequence of “if” statements

7 DFA : 예들 주어진 언어를 accept하는 DFA의 설계방법을 여러 가지 연습을 통해 이해할 것
- Ex 2.3 : ab로 시작하는 모든 string의 집합을 accept하는 DFA 설계 1 2 a b a, b 3 a,b - Ex 2.4 : 001을 포함하지 않는 모든 string을 accept하는 DFA 설계 l 00 1 001 0,1

8 DFA : Regular Languages
DFA가 accept하는 언어 Family를 정규언어라 함 - L : regular iff there exists some DFA M such that L = L(M) - To show L = regular  find a DFA for it - Ex 2.5 : L = {awa : w in {a, b}*} is regular? Point : no explicit way of testing the end of string  두번째 a가 나올 때마다 일단 final state로 가본다 2 b 3 a 1 a,b - Ex 2.6 : L2 is regular Point : aa가 나오면 두번째 DFA로 그림 2.7  L=regular -> L2, L3, … is regular

9 실전연습: 다음 언어 L을 인식하는 DFA를 설계하시오.
L = {x | x 는 binary 수이며 ( 즉, x  {0, 1}+), x mod 3 = 0} 힌트: 이 DFA의 idea는 입력으로 주어진 string을 한 bit 씩 우측으로 차례로 읽으며 지금까지 읽은 수에 대한 나머지를 계산해 두는 방법이다. Graph에서 state 상의 수는 지금까지 읽은 수를 3으로 나눈 나머지이다. 지금까지 읽은 수에 대한 나머지를 i 라 하자. 다음 읽은 bit가 j {0,1} 이면, 나머지는 (2i + j) mod 3 이다. 따라서 현 상태 i 상에서 j {0,1} 를 읽으면, 상태 (2i + j) mod 3 로 가도록 하면 된다. 1 2 start

10 DFA : Exercises (2.1) 2 : grammar와 오토메타에 대한 기초이해 문제
7 : DFA에 의한 modular counting 연습 (참고: 1.2절의 Exercise 14) 11, 12 : regular 언어란  해당 DFA 구축하기!! 20 : 정규언어의 특성(4장) 중 중요한 closure property에 대한 문제

11 NFA: 정의 Unique move대신에 set of possible move 허용 q0 q1 q2 a a,b b q0 q1 q2 a b X

12 NFA: 예 q0 q2 q5 a q3 q4 q1 q1 q0 1 λ 0,1 q2

13 NFA : Extended Transition Function
λ a q0 q2 q1

14 NFA : Language Acceptance

15 NFA: Nondeterminism? 왜 굳이 NFA를 사용하려 하는지에 대한 이해필요 q0 q2 q5 a q3 q4 q1

16 NFA: Exercises (2.2) 2 : DFA와 NFA의 equivalence에 대한 사전이해
15 : 약간 어려운 문제일까? 뒤의 해답을 참조하여 이해할 것

17 Equivalence of DFA & NFA
1 0,1 q0 q1 q2 q1 q0 1 λ 0,1 q2

18 NFA  DFA 기본 아이디어는 NFA의 상태수가 아무리 많아도 2|Q|개의 유한 수임을 이용한다 ø a a,b b
q1 q2 q0 λ a b q0 q2 q1

19 Theorem for NFADFA (1) 알고리즘과 종료함의 증명

20 Theorem for NFADFA (2) 동일함의 증명 by induction (8:2) Qi

21 NFADFA : 예 Ex 2.13 : 0,1 q0 q1 q2 1 q0 q1 q1 q0 q1 q2 q2 ø 0,1 1 q0
1 q0 q1 q1 q0 q1 q2 q2 ø 0,1 1 q0 q2 q1 L(MN) : regular NFA로 accept되는 언어도 regular임!

22 NFADFA : Exercises (2.3) 1 : 진짜 연습문제 5 : 이럴 경우, 8:2 rule에 의하면…?
- 13 : 주어진 언어가 무엇인지 먼저 파악할 것.

23 Reduction of Number of States
Simplicity, Storage efficiency Ex 2.14 : p.62 Inaccessible reachable

24 Mark Algorithm mark distinguishable pairs
Distinguishable states를 모두 찾아 내는 알고리즘 mark distinguishable pairs Thm : mark terminates & determines all distinguishable states  증명 : 8:2

25 Reduce Algorithm reduce indistinguishable state 구별이 안 되는 states를 모아서
a state

26 State Reduction : 예 q0 q2 q1 q4 0,1 1 q3 Ex) 4 123 0,1 1
1 q3 Ex) 4 123 0,1 1 증명 : 1) 동일한가? 8:2 by induction 2) Minimal? 이제 슬슬 8:2면?

27 State Reduction : Exercises (2.4)
2 : 골라서 2문제 정도는 연습할 것 4 : 뒤의 힌트를 참고하면…