[오토마타] Deterministic and Nondeterministic finite accepter

Deterministic finite accepter(이하 dfa)는 다음과 같은 5원소 쌍으로 정의된다.

• Q : 내부 상태(inter state)들의 유한 집합이다.
• ∑ : 심벌들의 유한 집합이며, 입력 알파벳이라 불린다.
• ∂ : 전이 함수(tansition function)
• q₀ : q₀ ∈ Q 이며, initial state이다.
• F : F ⊆ Q 이며, final state이다.

이는 아래와 같은 그림으로 나타 낼 수 있다.

 

 

 

 

state는 동그라미로 나타내며 이중 선으로 그려진 동그라미는 final state를 나타낸다. 화살표는 tansition을 나타내며, 전이 함수(∂)에 의해 transition이 정의된다. 이는 ∂(q_n, a∈∑) = q_m 로 나타 낼 수 있다.
위 그래프의 전이 함수를 나열 해 보면

• ∂(q₀, 1) = q₀
• ∂(q₀, 0) = q₁ (승인 상태)
• ∂(q₁, 1) = q₀
• ∂(q₁, 0) = q₁ (승인 상태)

와 같이 나타내여 진다.
dfa의 특징은, 하나의 state에서 ∑의 모든 원소에 대한 경로가 있어야 하고, 한 원소로 두가지 경로를 가리키지 못한다.
그리고 λ는 다른 state로의 transition이 될 수 없다. (항상 ∂(q, λ) = q이며, 그래프 상에 λ를 표현하지 않는다.)
dfa M에 의해 인식되는 언어란 M에 의해 승안되는 ∑에 대한 모든 문자열들의 집합니다. 아래와 같이 표현한다.

L(M) = {w∈∑^* : ∂^*(q₀, w) ∈ F}

그리고 언어 L에 대하여 L = L(M)을 만족하는 dfa M이 존재할 경우 이를 정규 언어(regular language)라 부른다.

 

Nondeterministic finite accepter(이하 nfa)는 dfa와 3가지 큰 차이점을 가진다.

1. nfa의 ∂의 치역은 Q의 부분집합이다. 그 말인 즉슨, 전이 함수의 결과가 여러개의 state가 될 수 있다는 것이다.
   ∂(q₁, a) = {q₀, q₁}
2. nfa에선 전이 함수의 두 번째 인자로 λ를 가질 수 있다. 즉 심벌 입력 없이도 이동이 가능 하다.
3. 특정 state에서 정의된 전이가 없을 수 있다. 즉 입력을 받고도 이동이 없을 수 있다.

 

위 nfa 그래프를 보면 a에 의해 두 갈래로 갈라져 있는 모습이 보인다. 이는 a로 양쪽 경로 모두 접근 가능한 것을 나타낸다.

그리고 q₁ 에서 q₂으로의 전이가 λ인 것을 확인 할 수 있다. 이는 w=aa 로도 final state로 도달이 가능 한것을 뜻한다. 이 λ-transition은 필요한 만큼 사용 가능하다. 그 말인 즉슨, λλaλaλλ, λλaλλaλb 는 모두 final state에 도달 가능한 적절한 경로이다.

마지막으로 ∑={a,b} 임에도 불구하고 b에 의한 전이가 정의되지 않은곳이 많다. 이는 해당 state에서 b입력이 들어 올 경우 그냥 머무는 것을 의미한다.