[Automata][WIP] Finite Automata - DFA, NFA

이번 포스팅에서는 Chapter 2의 내용을 다뤄보려고 한다. 

 

• Deterministic Automata: 현재 상태에 의해서 move가 결정된다. 
• Nondeterministic Automata: 여러개의 move가 있을 수 있다. 

DFA(Deterministic Finite Accepters): 결정적 유한 인식기

특징

• 내부 상태 개수가 유한하다. 
• input string은 심볼의 sequnce로 구성됨
• 한 state에서 다른 state로 transition 가능
• output이 있다

DFA의 정의 (1)

DFA는 다음과 같은 5개 원소의 tuple로 정의된다. 

 

M = (Q, Σ, 𝛿, q0, F)

 

• Q: 유한개의 internal state의 집합
• Σ: input alphabet
• 𝛿: Q ✖️Σ -> Q 는 transition function이라고 부르는 total function
  • ex) 𝛿(q0, a) = q1
• q0: initial state
• F: final state의 집합

Extended Transition Function: 𝛿*

𝛿* : Q ✖️Σ* -> Q

 

큰 모델도 쉽게 설명하기 위해서 등장한 함수..!

 

정의

𝛿*(q, w, a) = 𝛿(𝛿*(q, w), a)

 

만약 델타 스타가 갈 곳이 없다면 공집합이라고 표기한다. 

DFA의 Language

DFA M에 대하여, 

 

L(M) = {w ⊂ Σ* : 𝛿(q0, w) ⊂ F}

이면 DFA의 Language이다. 

Regular Language

L=L(M)을 만족하는 dfa M이 있을 경우 language L은 regular이다.  

---

NFA(Nondeterministic Finite Accepters): 비결정적 유한 인식기

같은 문자가 들어와도 여러개의 move가 가능한 경우이다. 

NFA의 정의

NFA는 다음과 같은 5개 원소의 tuple로 정의된다.

 

M = (Q, Σ, 𝛿, q0, F)

 

• Q: 유한개의 internal state의 집합
• Σ: input alphabet
• 𝛿: Q ✖️Σ -> Q 는 transition function이라고 부르는 total function
  • ex) 𝛿(q0, a) = q1
• q0: initial state
• F: final state의 집합

Extended Transition Function: 𝛿*

𝛿*(qi, w) = Qj

 

NFA에서도 나오던거!

 

정의

𝛿*(q, w, a) = 𝛿(𝛿*(q, w), a)

NFA의 Language

NFA M에 대하여, 

 

L(M) = {w ⊂ Σ* : 𝛿*(q0, w) ⊂ F != ∅}

이면 DFA의 Language이다. 

 

왜 Nondeterministic을 쓰는가?

 

더 간단하다?

기술적 이유: 어떤 이론들은 dfa보다 nfa가 훨씬 성립하기 쉽다!

 

---

DFA와 NFA의 동일성

사실 DFA와 NFA는 근본적인 차이가 없다고 한다. 

 

증명하기

nfa에서 dfa로 바꾸기

 

1. init: {q_0}가 initial vertex인 그래프를 만들어 준다. 

2. 반복하지 않은 선이 없을 때까지 반복해 준다. 

• 1. 임의의 문자 a에 대해서, 밖으로 나가는 선이 없는 vertex를 모두 고른다. 얘네가 i, j, ...k vertex라면,  𝛿*(qi, a), 𝛿*(qj, a), ...𝛿*(qk, a) 를 계산한다. 
• 2. 𝛿*(qi, a),𝛿*(qj, a), ...𝛿*(qk, a) 를 합집합 한 값으로 새로운 노드를 만들어 준다. 
• 3. qi, qj, ..., qk 로 부터 ql, qm, .., qn 으로 a edge를 그려준다.

3. 기존에 final state였던 node를 포함한 모든 node를 final vertex로 지정한다. 

4. ƛ ( 빈 문자열) 도 가능하다면 {q_0} 도 final vertex로 만들어준다. 

 

만약 dfa에 선이 없다면 자기 자신으로 보내는게 아니라 공집합 노드를 만들어서 그쪽으로 선을 연결해 줘야한다!!! 합집합 중 하나라도 선이 있으면 노드로 보내고, 집합 안에 아무도 요소가 없을 때 공집합으로 보낸다.