Finite Automata

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로 변환

1. 시작 상태에 대한 $\varepsilon$-closure를 구해서 하나의 상태로 정의 후 $D_s$에 넣는다.
2. $D_s$에 들어있는 상태 요소 하나를 꺼낸다.
3. 꺼낸 상태 요소에서 각 입력마다 도달할 수 있는 상태 집합을 구해 그 상태 집합에 대한 $\varepsilon$-closure를 구한다.
   1. 구해진 $\varepsilon$-closure 값이 정의되지 않은 상태이면 새로운 상태로 정의하고 $D_s$에 넣는다.
   2. 구해진 $\varepsilon$-closure 값이 이미 정의된 상태이면 그냥 넘어간다.
4. $D_s$가 빌 때까지 2,3번을 반복한다.
5. 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 찾기

1. 도달 가능한 상태 찾기
2. 도달 불가능한 상태 제거
3. 동일한 상태 찾기
   1. final state인 것과 아닌 것을 class로 나눔
   2. 각 상태에서 각 입력을 받았을 때 도달하는 상태가 해당하는 클래스를 구한다.
   3. 모든 입력에 대해 도달하는 클래스가 같은 것끼리 클래스를 다시 나눠준다.
   4. 클래스가 더 이상 나눠지지 않을 때까지 b, c 반복
   5. 같은 클래스인 상태들은 하나의 상태로 merge

정규표현과 NFA

• 정규 표현 R이 주어지면 $L_R$을 인식하는 NFA N을 만드는 알고리즘이 있다. $L_R = L(N)$
• $\uparrow$을 위한 가정
  1. 각 NFA는 시작 상태와 구분되는 하나의 final state를 가진다.
  2. 시작 상태로 들어가는 전이가 없고 마지막 상태에서 나가는 전이가 없다.
  3. 모든 상태는 최대 2개의 들어오는 전이와 2개의 나가는 전이가 있다.

Sombrero construction

• 기본
  • $R = a$

    

  • $R = \varepsilon$

    

  • $R = \varnothing$

    

• 재귀
  • $R_1 + R_2$

    

    

  • $R_1R_2$

    

  • $R^*$

    

NFA 단순화