[계산이론] - (4) 밀리기계(Mealy Machine), 무어기계(Moore Machine)

 

 

 

변환기(transducer)

변환기는 출력이 있는 유한 오토마타이며, 그 종류로는 밀리 기계와 무어 기계가 있습니다.

 

 

 

 

 

Mealy 기계(Mealy Machine, Transition-aasigned FSM)

밀리 기계에서는 각 전이에 의해 만들어지는 출력은

그 전이 이전의 내부 상태와, 전이에 사용되는 입력 심벌에 의해 결정됩니다.

 

Mealy 기계는 다음과 같이 정의됩니다.

$$ M = (Q, \Sigma, \Delta, \delta, \lambda, q_o)$$

 

여기서

Q : 내부 상태들의 유한 집합

Σ : 입력 알파벳(기호)의 집합

Δ : 출력 알파벳(기호)의 집합

δ : 전이 함수, Q x Σ -> Q

λ : 출력 함수, Q x Σ -> Δ

q0 : 초기 상태

 

전이 그래프는 유한 인식기에서와 마찬가지로 변환기에서도 유용한데, 밀리 기계의 전이 그래프의 예시를 하나 그려보겠습니다.

 

 

 

 

 

 

 

무어기계 (Moore Machine, State-assigned FSM)

무어 기계는 밀리 기계와 출력을 만드는 방식에 차이가 있습니다.

무어 기계에서는 각 상태는 출력 알파벳의 원소와 연관됩니다.

한 상태에 놓일 때마다, 그 상태에 연관된 심벌이 출력됩니다.

 

 

Moore 기계는 다음과 같이 정의됩니다.

$$ M = (Q, \Sigma, \Delta, \delta, \lambda, q_o)$$

 

여기서

Q : 내부 상태들의 유한 집합

Σ : 입력 알파벳(기호)의 집합

Δ : 출력 알파벳(기호)의 집합

δ : 전이 함수, Q x Σ -> Q

λ : 출력 함수, Q  -> Δ

q0 : 초기 상태

 

 

무어 기계의 예시입니다

 

 

 

 

 

 

 

 

 

무어기계와 밀리기계의 동치성

모든 무어기계에 대해 동치인 밀리기계가 존재하며 멱도 성립합니다.

 

두 개의 유한 상태 변환기 M과 N이 같은 함수를 구현한다면, 두 변환기가 동치라고 합니다.

두 변환기 M과 N이 같은 함수를 구현한다는 것은 두 변환기의 정의역이 같고, 그 공통 정의역에 속한 모든 원소 w에 대하여 

$$F_M(w) = F_N(w) \;임을 뜻합니다.$$

 

 

 

 

 

 

 

변환 방법

밀리기계를 무어기계로 바꾸는 간단한 방법은 다음과 같습니다.