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

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

개요 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

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

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

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

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

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

실전연습: 다음 언어 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

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

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

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

NFA : Extended Transition Function λ a q0 q2 q1

NFA : Language Acceptance

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

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

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

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

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

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

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임!

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

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

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

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

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면?

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