2つの重機の「結合」

どのように2台のミリアンペルマシンを組み合わせることができますか?最初の$ M_1 $は入力$ sum_ {1} ^ *
$と出力$ sum_ {2} ^ * $として、 2番目のマシン$ M_2 $は出力$ sum_ {2} ^ *
$を入力として使用し、$ sum_ {3} ^ * $を出力します。 それで$M_2◦M_1(w)$マシンが$ sum_
{1} ^ * $からの単語となる$M_2◦M_1(w)$マシンとは何ですか?

ベストアンサー

Mealyマシンは、状態集合$ S $、S $の初期状態$ s 、遷移関数$ A times S 〜B times
S $(これはアルファベット$ Aの文字を入力として取ります$と現在の状態$ S $とを比較し、$ B $から出力された出力文字と$
S $から更新された状態を生成する。

これをOcamlの型宣言として以下のように書くことができます:

type ('a,'b) mealy = M : 's * ('a * 's -> 'b * 's) -> ('a,'b) mealy

次に、次のような作成操作が行われます。

let compose : type a b c. (a,b) mealy -> (b,c) mealy -> (a,c) mealy = 
  fun (M(s, f)) (M(t, g)) -> 
    let state = (s,t) in 
    let trans (a, (s, t)) = 
      let (b, s') = f(a, s) in
      let (c, t') = g(b, t) in 
      (c, (s',t')) 
    in
    M(state, trans)

したがって、複合機械の状態は2つの状態集合の積であり、新しい初期状態は2つの初期状態の対であり、複合遷移関数は入力を第1の遷移関数に供給し、その出力を入力として使用する第2の遷移関数に変換する。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です