Finite Automata
2023. 9. 28. 05:47ㆍ전공/컴파일러
Finite automata
유한오토마타(Finite automata)
- 정규 언어인지 아닌지 판단하는 인식기
- 유한 전이 그래프
- 유한개의 상태들
- 특정 상태에서 어떤 입력을 받으면 다른 상태로 전이하는 것을 표현
- 시작 상태에서 목표 상태까지 도달이 가능하면 인식이 가능한 언어이고, 도달할 수 없으면 인식 불가능한 언어
- 정규 언어를 인식하는 수학적 모델
- 어휘분석기 사용
- Deterministic / Non-Deterministic finite automata
Deterministic finite automata(DFA)
- $D = (Q,\Sigma, \delta, q_0, F)$
- $Q$ : 상태들의 집합
- $\Sigma$ : 입력 기호(알파벳)들의 집합
- $\delta$ : 전이 함수, $\delta : Q \times \Sigma \rightarrow Q$
- $q_0$ : 시작 상태, $q_0 \in Q$
- $F$ : 마지막 상태의 집합, $F \subseteq Q$
- 어떤 상태 P에서 입력 a를 받았을 때 다음 상태 q로 가는 것은 확실히 한 군데로 결정됨
확장된 전이 함수 $\delta^*$의 정의
- $\delta^* : Q \times \Sigma^* \rightarrow Q$
- 전이함수를 여러 번 적용
- 모든 $p\in Q, u \in \Sigma^*, a \in \Sigma$
- 기본식 : $\delta^*(p, \varepsilon) = p$
- 유도식 : $\delta^(p, ua) = \delta(\delta^(p, u), a)$
- $\delta^*(p, w)$ : 상태 p에서 입력 w를 받아 도달할 수 있는 상태
DFA D에 의해 인식되는 언어 L(D)
- $L(D) = \{w \in \Sigma^* \space|\space\delta^*(q_0, w) \in F\}$
- 시작상태에서 w를 통해 도달하는 상태가 F에 포함되어 있는 모든 w들의 집합
- 시작 상태에서 입력 w에 따라 도달한 상태가 수용가능한 상태이면 인식 가능
Membership (recognition) problem
- 어떤 문자열 $w \in \Sigma^*$가 언어 L에 포함되는지 결정하고 싶음
- 주어진 문자열 $w \in \Sigma^*$가 DFA에 의해 수용가능한지 확인
- 시작상태 $q_0$에서 문자열 w에 포함되는 입력들을 받아 도달하는 상태를 계산
- w에 포함된 모든 입력을 수행한 후의 상태가 수용가능한 상태(F)이면 w는 수용되고, 그렇지 않으면 거부됨
Non-Deterministic finite automata(NFA)
- $N = (Q,\Sigma, \delta, q_0, F)$
- $Q$ : 상태들의 집합
- $\Sigma$ : 입력 기호(알파벳)들의 집합
- $\delta$ : 전이 함수, $\delta : Q \times (\Sigma \space \cup \space \{\varepsilon\}) \rightarrow 2^Q$(모든 부분집합을 표현할 수 있는 집합)
- $q_0$ : 시작 상태, $q_0 \in Q$
- $F$ : 마지막 상태의 집합, $F \subseteq Q$
- 어떤 상태 P에서 입력 a를 받았을 때 다음 상태는 Q의 부분집합 중 하나로 결정
- 여러 가지 상태로 전이 가능
- $\varepsilon$도 입력 가능
- 경로계산트리에서 수용가능한 경로가 존재하면 문자열 w는 수용되고, 모든 경로가 수용가능한 상태에 도달하지 않으면 w는 거부된다.
N에 의해 수용가능한 언어 L(N)
- $L(N) = \{w \in \Sigma^* \space | \space \delta^*(q_0, w) \space \cap \space F \not= \varnothing\}$
- 시작상태에서 입력 w에 따라 도달한 상태와 수용가능한 상태 F의 교집합이 공집합이 아니면 수용가능한 경로가 존재 → w 인식 가능
$\varepsilon$-closure
- NFA에서 모든 상태 p에 대해 p의 $\varepsilon$-closure($\varepsilon$-closure(p))은 p에서 $\varepsilon$을 입력받아 도달하는 모든 상태 q로 구성
- q = p 또는 p에서 $\varepsilon$을 입력받아 q로 이동하는 경로에 있는 모든 엣지들
- $\varepsilon-closure(p) = \{p\} \cup \{q \in Q | \exists s \in \varepsilon-closure(p), q \in \delta(s,\varepsilon)\}$
- $\varepsilon-closure(S) = \cup_{s\in S}\varepsilon-closure(s)$
확장된 전이 함수 $\delta^*$의 정의
- $\delta^* : Q \times \Sigma^* \rightarrow 2^Q$
- 모든 $p\in Q, u \in \Sigma^*, a \in \Sigma$
- 기본식 : $\delta^*(p, \epsilon) = \varepsilon-closure(\{p\})$
- 유도식 : $\delta^(p, ua) = \varepsilon-closure(\cup_{s\in\delta^(p,u)}\delta^*(s, a))$
- $\delta^*(p, w)$ : 상태 p에서 입력 w를 받아 도달할 수 있는 모든 상태들의 집합
NFA N에 의해 인식되는 언어 L(N)
- $L(N) = \{w \in \Sigma^* | \delta^*(q_0,w) \cap F \not= \varnothing\}$
- $\delta^(q_0, w)$가 final state를 1개 이상 포함하고 있다면 $w \in \Sigma^*$가 인식된다.
NFA와 DFA
- NFA로 인식 가능한 언어라면 DFA로도 인식 가능 L(D) = L(N)
- NFA와 DFA가 인식하는 것은 같음
- NFA는 DFA로 바꿀 수 있음
NFA를 DFA로 변환
- 시작 상태에 대한 $\varepsilon$-closure를 구해서 하나의 상태로 정의 후 $D_s$에 넣는다.
- $D_s$에 들어있는 상태 요소 하나를 꺼낸다.
- 꺼낸 상태 요소에서 각 입력마다 도달할 수 있는 상태 집합을 구해 그 상태 집합에 대한 $\varepsilon$-closure를 구한다.
- 구해진 $\varepsilon$-closure 값이 정의되지 않은 상태이면 새로운 상태로 정의하고 $D_s$에 넣는다.
- 구해진 $\varepsilon$-closure 값이 이미 정의된 상태이면 그냥 넘어간다.
- $D_s$가 빌 때까지 2,3번을 반복한다.
- NFA의 final state를 포함하는 상태를 DFA의 final state로 표시해 준다.
정규 언어와 DFA
- DFA에 의해 인식되면 그 언어는 정규 언어이다.
- 정규언어는 여러 개의 다른 DFA에 의해 인식될 수 있다.
Minimal DFA
- 언어 L을 인식하는 모든 DFA들 중 상태의 개수가 가장 적은 DFA
Reachability
- DFA는 시작 상태에서 도달할 수 없는 상태를 가질 수 있다. → 필요 없으므로 삭제
Reachable states
- DFA에서 도달 가능한 상태 $Q_r = \{p \in Q | (\exists u \in \Sigma^)(p=\delta^(q_0,u))\}$
- $Q_r$을 찾는 것이 reachability problem
- DFA에서 도달할 수 없는 상태들$(Q - Q_r)$을 제거
State Equivalence(상태 동등성)
- DFA에서 $\equiv$는 같은 상태를 나타냄
- 모든 p, q $\in$ Q, p $\equiv$ q iff $\forall w \in \Sigma^(\delta^(p,w) \in F$ iff $\delta^*(q,w) \in 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이 주어지면 $L_R$을 인식하는 NFA N을 만드는 알고리즘이 있다. $L_R = L(N)$
- $\uparrow$을 위한 가정
- 각 NFA는 시작 상태와 구분되는 하나의 final state를 가진다.
- 시작 상태로 들어가는 전이가 없고 마지막 상태에서 나가는 전이가 없다.
- 모든 상태는 최대 2개의 들어오는 전이와 2개의 나가는 전이가 있다.
Sombrero construction
- 기본
- $R = a$
- $R = \varepsilon$
- $R = \varnothing$
- 재귀
- $R_1 + R_2$
- $R_1R_2$
- $R^*$
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 |