Finite Automata
2023. 9. 28. 05:47ㆍ전공/컴파일러
Finite automata
유한오토마타(Finite automata)
- 정규 언어인지 아닌지 판단하는 인식기
- 유한 전이 그래프
- 유한개의 상태들
- 특정 상태에서 어떤 입력을 받으면 다른 상태로 전이하는 것을 표현
- 시작 상태에서 목표 상태까지 도달이 가능하면 인식이 가능한 언어이고, 도달할 수 없으면 인식 불가능한 언어
- 정규 언어를 인식하는 수학적 모델
- 어휘분석기 사용
- Deterministic / Non-Deterministic finite automata
Deterministic finite automata(DFA)
- D=(Q,Σ,δ,q0,F)
- Q : 상태들의 집합
- Σ : 입력 기호(알파벳)들의 집합
- δ : 전이 함수, δ:Q×Σ→Q
- q0 : 시작 상태, q0∈Q
- F : 마지막 상태의 집합, F⊆Q
- 어떤 상태 P에서 입력 a를 받았을 때 다음 상태 q로 가는 것은 확실히 한 군데로 결정됨
확장된 전이 함수 δ∗의 정의
- δ∗:Q×Σ∗→Q
- 전이함수를 여러 번 적용
- 모든 p∈Q,u∈Σ∗,a∈Σ
- 기본식 : δ∗(p,ε)=p
- 유도식 : δ(p,ua)=δ(δ(p,u),a)
- δ∗(p,w) : 상태 p에서 입력 w를 받아 도달할 수 있는 상태
DFA D에 의해 인식되는 언어 L(D)
- L(D)={w∈Σ∗ | δ∗(q0,w)∈F}
- 시작상태에서 w를 통해 도달하는 상태가 F에 포함되어 있는 모든 w들의 집합
- 시작 상태에서 입력 w에 따라 도달한 상태가 수용가능한 상태이면 인식 가능
Membership (recognition) problem
- 어떤 문자열 w∈Σ∗가 언어 L에 포함되는지 결정하고 싶음
- 주어진 문자열 w∈Σ∗가 DFA에 의해 수용가능한지 확인
- 시작상태 q0에서 문자열 w에 포함되는 입력들을 받아 도달하는 상태를 계산
- w에 포함된 모든 입력을 수행한 후의 상태가 수용가능한 상태(F)이면 w는 수용되고, 그렇지 않으면 거부됨
Non-Deterministic finite automata(NFA)
- N=(Q,Σ,δ,q0,F)
- Q : 상태들의 집합
- Σ : 입력 기호(알파벳)들의 집합
- δ : 전이 함수, δ:Q×(Σ ∪ {ε})→2Q(모든 부분집합을 표현할 수 있는 집합)
- q0 : 시작 상태, q0∈Q
- F : 마지막 상태의 집합, F⊆Q
- 어떤 상태 P에서 입력 a를 받았을 때 다음 상태는 Q의 부분집합 중 하나로 결정
- 여러 가지 상태로 전이 가능
- ε도 입력 가능
- 경로계산트리에서 수용가능한 경로가 존재하면 문자열 w는 수용되고, 모든 경로가 수용가능한 상태에 도달하지 않으면 w는 거부된다.
N에 의해 수용가능한 언어 L(N)
- L(N)={w∈Σ∗ | δ∗(q0,w) ∩ F≠∅}
- 시작상태에서 입력 w에 따라 도달한 상태와 수용가능한 상태 F의 교집합이 공집합이 아니면 수용가능한 경로가 존재 → w 인식 가능
ε-closure
- NFA에서 모든 상태 p에 대해 p의 ε-closure(ε-closure(p))은 p에서 ε을 입력받아 도달하는 모든 상태 q로 구성
- q = p 또는 p에서 ε을 입력받아 q로 이동하는 경로에 있는 모든 엣지들
- ε−closure(p)={p}∪{q∈Q|∃s∈ε−closure(p),q∈δ(s,ε)}
- ε−closure(S)=∪s∈Sε−closure(s)
확장된 전이 함수 δ∗의 정의
- δ∗:Q×Σ∗→2Q
- 모든 p∈Q,u∈Σ∗,a∈Σ
- 기본식 : δ∗(p,ϵ)=ε−closure({p})
- 유도식 : δ(p,ua)=ε−closure(∪s∈δ(p,u)δ∗(s,a))
- δ∗(p,w) : 상태 p에서 입력 w를 받아 도달할 수 있는 모든 상태들의 집합
NFA N에 의해 인식되는 언어 L(N)
- L(N)={w∈Σ∗|δ∗(q0,w)∩F≠∅}
- δ(q0,w)가 final state를 1개 이상 포함하고 있다면 w∈Σ∗가 인식된다.
NFA와 DFA
- NFA로 인식 가능한 언어라면 DFA로도 인식 가능 L(D) = L(N)
- NFA와 DFA가 인식하는 것은 같음
- NFA는 DFA로 바꿀 수 있음
NFA를 DFA로 변환
- 시작 상태에 대한 ε-closure를 구해서 하나의 상태로 정의 후 Ds에 넣는다.
- Ds에 들어있는 상태 요소 하나를 꺼낸다.
- 꺼낸 상태 요소에서 각 입력마다 도달할 수 있는 상태 집합을 구해 그 상태 집합에 대한 ε-closure를 구한다.
- 구해진 ε-closure 값이 정의되지 않은 상태이면 새로운 상태로 정의하고 Ds에 넣는다.
- 구해진 ε-closure 값이 이미 정의된 상태이면 그냥 넘어간다.
- Ds가 빌 때까지 2,3번을 반복한다.
- NFA의 final state를 포함하는 상태를 DFA의 final state로 표시해 준다.
정규 언어와 DFA
- DFA에 의해 인식되면 그 언어는 정규 언어이다.
- 정규언어는 여러 개의 다른 DFA에 의해 인식될 수 있다.
Minimal DFA
- 언어 L을 인식하는 모든 DFA들 중 상태의 개수가 가장 적은 DFA
Reachability
- DFA는 시작 상태에서 도달할 수 없는 상태를 가질 수 있다. → 필요 없으므로 삭제
Reachable states
- DFA에서 도달 가능한 상태 Qr={p∈Q|(∃u∈Σ)(p=δ(q0,u))}
- Qr을 찾는 것이 reachability problem
- DFA에서 도달할 수 없는 상태들(Q−Qr)을 제거
State Equivalence(상태 동등성)
- DFA에서 ≡는 같은 상태를 나타냄
- 모든 p, q ∈ Q, p ≡ q iff ∀w∈Σ(δ(p,w)∈F iff δ∗(q,w)∈F) 모든 w에 대해 q에서 w를 입력받아 도달한 상태가 final state에 포함될 때 p에서 w를 입력받아 도달한 상태가 final state에 포함되면 p는 q와 같다.
- p와 q가 같을 때 p와 q는 구별 불가능
Minimal DFA 찾기
- 도달 가능한 상태 찾기
- 도달 불가능한 상태 제거
- 동일한 상태 찾기
- final state인 것과 아닌 것을 class로 나눔
- 각 상태에서 각 입력을 받았을 때 도달하는 상태가 해당하는 클래스를 구한다.
- 모든 입력에 대해 도달하는 클래스가 같은 것끼리 클래스를 다시 나눠준다.
- 클래스가 더 이상 나눠지지 않을 때까지 b, c 반복
- 같은 클래스인 상태들은 하나의 상태로 merge
정규표현과 NFA
- 정규 표현 R이 주어지면 LR을 인식하는 NFA N을 만드는 알고리즘이 있다. LR=L(N)
- ↑을 위한 가정
- 각 NFA는 시작 상태와 구분되는 하나의 final state를 가진다.
- 시작 상태로 들어가는 전이가 없고 마지막 상태에서 나가는 전이가 없다.
- 모든 상태는 최대 2개의 들어오는 전이와 2개의 나가는 전이가 있다.
Sombrero construction
- 기본
- R=a
- R=ε
- R=∅
- R=a
- 재귀
- R1+R2
- R1R2
- R∗
- R1+R2
NFA 단순화

'전공 > 컴파일러' 카테고리의 다른 글
Lex (0) | 2023.09.28 |
---|---|
Lexical analysis (0) | 2023.09.28 |
Regular expression (0) | 2023.09.28 |
Formal Language, Grammar and Automata (0) | 2023.09.28 |
Introduction to Compiler (0) | 2023.09.28 |