![[6. Lexer (2).pdf]]
# Part 3. RE → FSM
## 예제
### 단일 문자: RE $a$가 표현하는 언어를 받아들이는 FSM?
![[단일문자.png|278]]
![[fsm_min_a-2.png|395]]
### Kleene Star: Re $a^*$이 표현하는 언어를 받아들이는 FSM?
![[fsm_min_a_.png|417]]
### $(0|1)^*0$: RE $(0|1)^*0$이 표현하는 언어를 받아들이는 FSM?
![[fsm_min__0_1__0-2.png|419]]
## 아이디어: $\epsilon$ 의 활용
- 있든 없든 상관없음
## Thomson's Construction
### RE를 FSM으로 표현하는 알고리즘
- 귀납적으로 정의된 알고리즘
- `왜?` RE가 귀납적으로 정의됨
- 각각의 경우에 다음의 2가지를 만족하는 방법 제시
1. RE를 FSM으로 표현 가능
2. 표현된 FSM은 1개의 start state, 1개의 final state를 가짐
### Base Case: $\epsilon$ & $a$
Thomson's Construction
초록색 박스 안에는 모르는 state 변화라고 이해하면 되는지?
### Thomson's Construction의 성질
1. 각각의 State에 대해 최대 2개의 $\epsilon$-transition과 1개의 알파벳 transition이 존재
1. $\epsilon$-transition: $\epsilon$을 입력으로 받아 생기는 transition
2. $O(n)$의 시간/공간 복잡도
1. $n$: RE의 크기
### NFA (Non-deterministic Finite Automata)
- NFA는 5-tuple ($\Sigma, S, s_0, \delta, F$)로 정의
- $\Sigma$: Alphabet 집합
- $S$: State들의 **유한** 집합
- $s_0$: 시작을 나타내는 특별한 state ($s_0 \in S$)
- $\delta$: state의 transition을 나타내는 함수 ($\delta: S \times (\Sigma \cup \{\epsilon\}) \to \wp(S)$)
- $\wp(S)$: $S$의 **Power Set
- $F$: 마지막 상태들의 집합
### Thomson's Construction: RE → NFA
### 문제: NFA는 비효율적
- 문제의 원인: $\epsilon$-transition
- $\epsilon$으로 갈 수 있는 것들을 모아서 합치면 됨
## DFA(Deterministic Finite Automata)
- DFA는 5-tuple ($\Sigma, S, s_0, \delta, F$)로 정의
- $\Sigma$: Alphabet 집합
- $S$: State들의 **유한** 집합
- $s_0$: 시작을 나타내는 특별한 state ($s_0 \in S$)
- $\delta$: state의 transition을 나타내는 함수 ($\delta: S \times \Sigma \to S$)
- $F$: 마지막 상태들의 집합
- 한 transition을 통해 한 state($S$의 원소)에 갈 수 있음, 즉 **deterministic**
## Subset Construction
### 아이디어: $\epsilon$-transition을 없애야 함
- `how?` $\epsilon$-transition으로 도달 가능한 모든 state를 새로운 FSM의 state로 정의
- $\epsilon$-closure(s): state $s \in S$로부터 $\epsilon$-transition으로 도달 가능한 모든 state들의 집합
### Initial / Final State
- 새로운 state가 원래 state의 initial state를 가지고 있으면 Initial
- 새로운 state가 원래 state의 final state를 가지고 있으면 Final
### Subset Construction
> NFA $(\Sigma, S, s_0, \delta, F)$ $\to$ DFA$(\Sigma, Q, q_0, |Delta, F')$
### Subset Construction Algorithm
```
q₀ ← ε-Closure({s₀}), Q ← {q₀}, WorkList ← {q₀}
while (WorkList != ∅) do
WorkList, q ← pop(WorkList)
for (a ∈ Σ) do
q' ← ε-Closure(δ(q, a))
if (q' != ∅) then
if (q' ∉ Q) then
Q ← Q ∪ {q'}, WorkList ← WorkList ∪ {q'}
Δ(q, a) ← q'
```
- 유한하기에 (Finite State Machine) 끝나기는 끝남
- 빠른 알고리즘은 X, WorkList 알고리즘
### WorkList Algorithm
- 처리해야 할 것들의 목록 확인 → 새로 발견한 것 추가 → 새로운 것 없으면 종료
- 예시: BFS
### BFS
```
WorkList ← {start}, visited ← {}
while WorkList != ∅ do
WorkList, node ← pop(WorkList)
if node ∉ visited then
visited ← visited ∪ {node}
// Do something here
for neighbor ∈ neighbors(node) do
WorkList ← WorkList ∪ {neighbor}
```
→ 적용하면 아래 Subset Construction Algorithm
# ☑️☑️☑️ 알고리즘 이해하기
# Part 4. Lexer의 구현
---
0이 들어왔을 때 뭐 어디로 가야 할지 모르겠음 NFA
ε으로 갈 수 있는 곳이 어딘지 먼저 보기.. 그 이후에는 s3도 있고 s8도 있음. 어디로 가야 할지 모르겠음. -> 문제의 원인 == ε-transition
DFA가 이걸 해결...
어떻게 NFA를 DFA로 변환시키는가? Subset construction
ε-closure ε으로 도달 가능한 모든 state들의 집합.
underlined state는 원래 FSM / DFA의 state는 Bold 처리
s3, s8 둘 다 갈 수 있는 0이니까 하나로 뭉침
state set은 달라짐 (S, Q) -> initial state도 달라지고 transition도 달라지고 final state도 달라짐.
끝난다.
FSM은 유한한 state를 가진다.
한 단계가 지나면, 점점 집합의 크기가 커진다. 그 다음 단계가 되면 커질 것 같음. 만날 때마다 커지니까 NFA의 state 개수는 유한함.
BFS. 최대 크기 = 전체 상태 수
Subset construction으로 뭘 만드냐?
NFA의 부분집합을 가지고 새로운 state를 만듦.
NFA 상태 개수가 n개면
👉 만들 수 있는 subset 개수는 **최대 2^n 개**