밀리머신

계산 이론에서, 밀리 기계는 현재 상태와 전류 입력에 의해 모두 출력 값이 결정되는 유한 상태 기계입니다.이는 출력 값이 현재 상태에 따라 결정되는 Moore 기계와는 대조적입니다.Mailey 기계는 결정론적 유한 상태 변환기입니다. 각 상태와 입력에 대해 최대 한 번의 전환이 가능합니다.

역사

Maley 기계는 1955년 논문 "A Method for Synthisential Circuits"^[1]에서 개념을 제시한 George H. Maley의 이름을 따서 명명되었다.

형식적 정의

Mailey 머신은 6개의 태플$S, S$ 0$,$ $G)로, 다음과$같이 $구성됩니다$$.$

• 유한 상태 $(\displaystyle$ S$)$
• 시작 상태(초기 상태라고도 함) ${\displaystyle {S\mathrm{}}_{}}$ 0$(\$$displaystyle$$S_{0$$})$$S$의 $요소{\displaystyle }$
• $입력$ 알파벳$δ$라고 하는 유한 집합
• 출력 알파벳$\delta {\displaystyle \mathrm{}}$(\$displaystyle\Lambda)$라는 유한 집합
• ${\displaystyle \mathrm{전이}}$ $함수{\displaystyle }$T :${\displaystyle }$S × ${\displaystyle \delta }$ ${\displaystyle \to }$S \ $displaystyle$ T$:$$S\times$ \$Sigma \rightarrow$ S$}$ 상태$$ 쌍과 입력 기호를 대응하는 다음 상태로 매핑합니다.
• 출력 $함수{\displaystyle }$G :${\displaystyle S}$ × ${\displaystyle \mathrm{\sigma }}$ ${\displaystyle \to }$ \ $displaystyle$G :$상태$와 입력$심볼$의 쌍을 $대응$하는 출력 심볼에 $매핑하는$ S\times \Sigma$$ \rightarrow \$Lambda }.$

일부 공식에서 전이 및 출력 함수는 $단일{\displaystyle }$ 함수 T${\displaystyle :S}$ × ${\displaystyle \delta }$ ${\displaystyle \to }$ S ×$$ \ $displaystyle$ T$:$로 통합된다.$S\times$ \$Sigma \오른쪽 화살표$ S$\times \Lambda$

Maly 머신과 Moore 머신의 비교

1. 가느다란 머신의 상태는 적은 경향이 있습니다.
   • 상태(n)가 아닌 호(n²)에 대한 출력이 다릅니다.
2. 무어 머신을 사용하는 것이 보다 안전합니다.
   • 출력은 클럭 에지에서 변경됩니다(항상 한 사이클 늦게).
   • Maly 머신에서는 입력 변경으로 인해 로직이 실행되자마자 출력이 변경될 수 있습니다.두 머신이 상호 접속되어 있을 때는 큰 문제가 됩니다.또한 주의하지 않으면 비동기 피드백이 발생할 수 있습니다.
3. 가느다란 기계는 입력에 더 빠르게 반응합니다.
   • 동일한 사이클로 반응합니다. 시간을 기다릴 필요가 없습니다.
   • Moore 기계에서는 상태를 출력으로 디코딩하는 데 더 많은 로직이 필요할 수 있습니다. 즉, 클럭 에지 이후 게이트 지연이 더 많습니다.

도표

Maley 기계의 상태 다이어그램은 출력 값을 각 상태와 연결하는 Moore 기계의 상태 다이어그램과 달리 출력 값을 각 전환 에지에 연결합니다.

입력 및 출력 알파벳이 모두 Ω일 경우, Mily automata에 Helix 방향^{[clarification needed]} 그래프(S × Ω, (x, i) → (T(x, i), G(x, i)))^[2]를 연결할 수도 있다.이 그래프는 상태와 문자의 쌍을 꼭지점으로 하고, 각 노드는 out-degree 1이며, (x, i)의 후속 노드는 오토마타의 다음 상태와 오토마타가 instate x에서 문자 i를 읽을 때 출력하는 문자입니다.이 그래프는 자동화가 이중화^{[definition needed]} 가능한 경우 분리 주기의 결합입니다.

예

간단하죠.

단순한 Maly 머신에는 입력과 출력이 각각1개씩 있습니다.각 전환 에지에는 입력 값(빨간색으로 표시)과 출력 값(파란색으로 표시)이 라벨로 지정됩니다.기계는 상태_i S에서 시작합니다(이 예에서는 출력이 가장 최근의 두 입력 값 중 배타적 또는 배타적이어야 합니다. 따라서 기계는 에지 디텍터를 구현하여 입력이 플립될 때마다 1을 출력하고 그렇지 않으면 0을 출력합니다).

복잡한

보다 복잡한 Maly 머신에는, 복수의 입력과 복수의 출력이 있습니다.

적용들

밀링 머신은 암호 기계에 기초적인 수학적 모델을 제공합니다.예를 들어 입력 및 출력 알파벳을 고려하여 Mily 머신은 문자열(입력 시퀀스)이 지정된 문자열(출력 시퀀스)로 처리할 수 있도록 설계할 수 있습니다.그러나 밀리 모델을 사용하여 Enigma를 설명할 수 있지만 상태 다이어그램은 너무 복잡하여 복잡한 암호화 기계를 설계하는 실행 가능한 수단을 제공할 수 없습니다.

Moore/Mealy 머신은 클럭의 어느 눈금에도 출력되는 DFA입니다.현대의 CPU, 컴퓨터, 휴대전화, 디지털 시계 및 기본적인 전자 기기/기계는 이를 제어하는 일종의 유한 상태 기계를 가지고 있습니다.

단순한 소프트웨어 시스템, 특히 정규식을 사용하여 나타낼 수 있는 시스템은 유한 상태 기계로 모델링할 수 있습니다.자판기나 기본적인 전자제품과 같은 간단한 시스템들이 많이 있다.

2개의 유한 상태 머신의 교차점을 찾는 것으로, 예를 들면 메시지를 교환하는 매우 간단한 동시 시스템을 설계할 수 있습니다.예를 들어, 신호등은 다른 신호등과 같이 동시에 작동하는 여러 개의 서브시스템으로 구성된 시스템입니다.

응용 프로그램의 몇 가지 예:

• 번호 분류
• 타이머로 감시하다
• 자판기
• 신호등
• 바코드 스캐너
• 가스 펌프

「 」를 참조해 주세요.

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

각주

레퍼런스

• Mealy, George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. pp. 1045–1079.
• Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press. ISBN 0-521-60492-3. Zbl 0489.68046.
• Roth, Charles H., Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. pp. 364–367. ISBN 0-534-37804-8.
• Akhavi, Ali; Klimann, Ines; Lombardy, Sylvain; Mairesse, Jean; Picantin, Matthieu (2012). "On the finiteness problem for automaton (semi)groups". International Journal of Algebra and Computation. 22 (6). arXiv:1105.4725. Bibcode:2011arXiv1105.4725A. Zbl 1280.20038.

외부 링크

• Wikimedia Commons의 Maly 머신 관련 미디어