Replicated

DFA의 상태수 최소화(state minimization)- DFA를 이용하는 어휘분석기의 상태 전이표의 크기를 줄임- 기억 공간을 적게 차지하도록 하고 어휘분석 프로그램을 간단히 하는데 큰 도움- 상태수를 최소화하는 방법: 동치관계(equivalance relation)를 이용 상태수에 합침(state merge) 구별 가능(distinguishable)- 문자열 w ∈ Σ* 에 대해, 만약 q1 상태에서 w를 모두 본 상태가 q3고 q2에서 w를 모두 본 상태가 q4일 때, q3, q4 중 하나만 종결 상태에 속하면 2개의 상태 q1과 q2는 구별 가능하다고 함 구별 불가능(Indistinguishable)- 문자열 w ∈ Σ* 에 대해, 만약 q1 상태에서 w를 모두 본 상태가 q3고 q2에서 w를..

NFA를 DFA로 변환1. ε-전이가 있는 NFA를 DFA로 변환2. ε-전이가 없는 NFA를 DFA로 변환* ε-전이 -> 입력 없이 이동 가능한 경로 ε-전이가 있는 NFA를 DFA로 변환- 이 변환은 ε-closure를 이용하여 변환- NFA에서 의미가 같은 여러 상태들이 DFA에서 하나의 상태로 변환된다는 것 ε-closure 어떤 상태에서 ε 전이만 따라갔을 때 도달할 수 있는 모든 상태들의 집합 (시작 상태 포함)= 간단하게, ε만 타고 갈 수 있는 모든 상태를 한 번에 묶은 것 1. S가 한 개의 상태일 경우- ε-closure(S)는 NFA의 상태 S와 상태 S로부터 레이블이 ε인 간선으로 도달될 수 있는 모든 상태들의 집합- 이 방법은 ε-closure(S)의 원소가 변하지 않을 때까지..

결정적 유한 오토마타 (DFA)DFA는 다음 두 가지 조건을 만족해야 함1. ε에 의한 상태 전이가 없고2. δ(q,a) = {P1, P2, ..., Pn}에서 n = 1 이다즉, δ : Q x Σ -> Q 하나의 입력 기호에 대해 다음 상태는 오직 하나이거나 상태 전이가 없어야 함 ε에 의한 상태 전이를 ε-전이라고도 함 ex.0과 1이 짝수 개인 문자열을 받아들이는 유한 오토마타가 DFA인지 알아보고 상태 전이도로 표현M = ( Q, Σ, δ, q0, F ) Q = {q0, q1, q2, q3}Σ = {0, 1}q0 = q0F = {q0} 상태전이도 δ01q0q2q1q1q3q0q2q0q3q3q1q2상태전이표 그런데 이 방식은 한 문자 한 문자 받아들여서, 전체 문자열이 한 번에 어디로 가는지 알기 ..