밀리 기계

계산 이론에서 밀리 기계 또는 밀리 머신(Mealy machine)은 현재 상태와 현재 입력에 따라 출력값이 결정되는 유한 상태 기계이다. 이는 출력값이 현재 상태에 의해서만 결정되는 무어 기계와 대조된다. 밀리 기계는 결정론적 유한 상태 변환기로, 각 상태와 입력에 대해 최대 하나의 전이만 가능하다.

역사
밀리 기계는 1955년 "순차 회로 합성을 위한 방법"(A Method for Synthesizing Sequential Circuits)이라는 논문에서 이 개념을 발표한 조지 H. 밀리의 이름을 따서 명명되었다.

형식적 정의
밀리 기계는 다음으로 구성된 6-튜플 이다:
 상태의 유한 집합 
 의 요소인 시작 상태 (또는 초기 상태) 
 입력 알파벳이라 불리는 유한 집합 
 출력 알파벳이라 불리는 유한 집합 
 상태와 입력 기호 쌍을 해당 다음 상태로 매핑하는 전이 함수 .
 상태와 입력 기호 쌍을 해당 출력 기호로 매핑하는 출력 함수 .

일부 공식화에서는 전이 함수와 출력 함수가 단일 함수 로 합쳐진다.

"시간에 따른 진화"는 이 추상화에서 상태 기계가 이산적인 "타이머 틱" 에서 시간에 따라 변하는 입력 기호를 참조하고, 이 이상적인 순간의 내부 구성에 따라 반응하거나, 상태 기계가 다음 입력 기호를 기다렸다가(FIFO에서처럼) 도착할 때마다 반응함으로써 실현된다.

밀리 기계와 무어 기계의 비교
 밀리 기계는 더 적은 상태를 가지는 경향이 있다:
 상태(n)보다는 아크(n2)에서 다른 출력을 가진다.
 전자 회로로 구현될 때 (수학적 추상화나 코드보다는):
 무어 기계는 밀리 기계보다 사용하기에 더 안전하다:
 출력은 클록 에지에서 변경된다 (항상 한 주기 늦게).
 밀리 기계에서는 논리가 완료되는 즉시 입력 변경이 출력 변경을 유발할 수 있다 — 두 기계가 상호 연결될 때 큰 문제이며, 주의하지 않으면 비동기 피드백이 발생할 수 있다.
 밀리 기계는 입력에 더 빠르게 반응한다:
 같은 주기 내에 반응한다 — 클록을 기다릴 필요가 없다.
 무어 기계에서는 상태를 출력으로 디코딩하는 데 더 많은 논리가 필요할 수 있다 — 클록 에지 이후에 더 많은 게이트 지연이 발생한다.

다이어그램
밀리 기계의 상태도는 각 전이 에지에 출력 값을 연결하며, 이는 각 상태에 출력 값을 연결하는 무어 기계의 상태도와 대조된다.

입력 및 출력 알파벳이 모두 인 경우, 밀리 오토마타에는 헬릭스 유향 그래프 도 연결할 수 있다.Akhavi et al (2012) 이 그래프는 상태와 문자의 쌍을 꼭짓점으로 가지며, 각 노드는 차수가 1이고, 의 후속 노드는 오토마타의 다음 상태와 오토마타가  상태에 있고  문자를 읽을 때 출력하는 문자이다. 이 그래프는 오토마타가 양방향 가역이면 분리된 순환들의 합집합이다.

예시

간단한 예시
섬네일|169px|하나의 입력과 하나의 출력을 가진 간단한 밀리 기계의 상태도. (모든 입력 값에 대해 현재 입력 값이 이전 값과 다르면 1을 출력하고, 그렇지 않으면 0을 출력한다.)
간단한 밀리 기계는 하나의 입력과 하나의 출력을 가진다. 각 전이 에지에는 입력 값(빨간색으로 표시)과 출력 값(파란색으로 표시)이 레이블링되어 있다. 기계는 상태 에서 시작한다. (이 예시에서 출력은 가장 최근의 두 입력 값의 배타적 OR이며, 따라서 기계는 입력이 바뀔 때마다 1을 출력하고 그렇지 않으면 0을 출력하는 에지 검출기를 구현한다.)

복잡한 예시
더 복잡한 밀리 기계는 여러 입력과 여러 출력을 가질 수 있다.

응용
밀리 기계는 암호화 기계에 대한 기본적인 수학적 모델을 제공한다. 예를 들어, 입력 및 출력 알파벳을 라틴 음소문자로 고려하면, 문자열(입력 시퀀스)이 주어졌을 때 이를 암호화된 문자열(출력 시퀀스)로 처리할 수 있는 밀리 기계를 설계할 수 있다. 그러나 밀리 모델을 에니그마 기계를 설명하는 데 사용할 수 있더라도, 상태도가 너무 복잡하여 복잡한 암호화 기계를 설계하는 데 실용적인 수단을 제공하지 못할 것이다.

무어/밀리 기계는 클록의 매 틱마다 출력을 내는 DFAs이다. 현대의 CPU, 컴퓨터, 휴대폰, 디지털 시계 및 기본적인 전자 장치/기계는 이를 제어하기 위한 일종의 유한 상태 기계를 가지고 있다.

특히 정규 표현식을 사용하여 표현할 수 있는 간단한 소프트웨어 시스템은 유한 상태 기계로 모델링할 수 있다. 자판기나 기본적인 전자 기기와 같이 이러한 간단한 시스템이 많이 있다.

두 유한 상태 기계의 교차점을 찾음으로써, 예를 들어 메시지를 교환하는 동시 시스템을 매우 간단한 방식으로 설계할 수 있다. 예를 들어, 신호등은 서로 다른 신호등과 같이 여러 하위 시스템으로 구성된 시스템이며, 이들은 동시에 작동한다.

 같이 보기 
 동기 회로
 무어 기계
 알고리즘 상태 기계
 리처드 컨트롤러

 내용주 

 각주 

 외부 링크 

분류:계산 모형
분류:유한 상태 기계