mealy machine in ocaml

Question

두 개의 구성을 가지고 싶습니다 Mealy machines과 두 finite state transducers. Mealy 기계/변환기를 ocaml로 표현하는 방법은 무엇입니까?

Answer 1

이전 질문과 관련하여 Nicollet's answer의 문제점은 무엇입니까? output : 'state * 'letter -> 'output 회원을 레코드에 추가하기 만하면됩니다.

Answer 2

답장에서 선택한 유형이 적합하지 않습니다.

type ('state,'letter) mealy = { 
    initial : 'state ; 
    final  : 'state -> bool ; 
    transition : 'letter -> 'state -> 'letter -> 'state ; 
} 

사실, 당신의 전환은 는는 출력을 생성하지 않습니다하지만 당신이 도달되는 상태를 알고 그것을 사용합니다. 수학적 단어에서 $ (I, Q) \ rightarrow (O, Q) $ 대신 $ (I, Q, O) \ rightarrow Q $ 유형의 전이 함수를 제공합니다. Curryfication을 사용하면 $ I \ rightarrow Q \ rightarrow (O, Q) $를 쓸 수 있지만 마지막 커플 유형은 펼칠 수 없습니다. 결과적으로 귀하가 존재하지 않는 d을 소개 한 이후로 귀하의 구성이 잘못되었습니다.

1. 예 'state -> 'letter -> ('letter * 'state) 같은 올바른로 전이 함수의 형식을 변경 이미
2. 제안 Gasche로서 출력 기능 추가 :

   당신은 this post의 오토마타 용액으로부터 두 용액이있다.

따라서 합성 기능을 제공 할 수 있습니다.

Answer 3

tulip 패키지에 Mealy 트랜스 듀서 python 구현 here을 연구 할 수 있습니다. Moore 기계는 엄밀히 말하자면 Mealy 기계인데, 자세한 내용은 this book을 참조하십시오 (대부분의 작성자가 잘못 이해하여 여기에서 언급 한 이유가 있습니다.) Moore 기계가 초기에 참으로 정의 된 것을 확인할 수 있습니다. 무어).

구성 할 때 상황이 매우 까다로워집니다. 계단식 동기 구성을 의미하는 경우 피드백 연결이 없기 때문에 결과를 쉽게 계산할 수 있습니다. 그러나 "구성"으로 피드백 구성을 참조하는 경우, 의미를 선택해야합니다. 예를 들어 동기 반응 의미론을 사용하면 컴포지션의 결과가 각 시간 단계에 대한 고정 소수점 솔루션으로 정의됩니다 (주제에 대한 포인터는 위에 인용 된 책 참조).

트랜스 듀서가 모두 밀리 (Mealy) 인 경우 고정 점 솔루션이 필요합니다. 그 이유는 둘 다 밀접한 관계가 없기 때문입니다. 즉 현재 출력은 현재 입력에 의존 할 수 있습니다. 대조적으로, 무어 기계는 엄격하게 인과 관계입니다 (엄격하게 인과 관계가있는 모든 밀 기계는 무어 기계입니다. 그러나 엄밀히 말하면, 밀 기계는 동일한 무어 기계가 존재하지 않습니다). Mealy 머신으로 무어 머신을 구성하는 것은 결과를 시뮬레이션하기 위해 고정 소수점 계산을 요구하지 않습니다.