Automata-theory-moore-and-mealy-machines
ムーア機とミーリー機
有限オートマトンには、各遷移に対応する出力がある場合があります。 出力を生成する有限状態マシンには2種類あります-
- ミーリーマシン
- ムーア機
ミーリーマシン
Mealy Machineは、出力が現在の状態と現在の入力に依存するFSMです。
6タプル（Q、∑、O、δ、X、q〜0〜）で記述できます。
- Q は有限状態のセットです。
- ∑ は、入力アルファベットと呼ばれる有限の記号セットです。
- O は、出力アルファベットと呼ばれる記号の有限セットです。
- *δ*は入力遷移関数です。δ：Q×input→Q
- X は出力遷移関数です。X：Q×∑→O
- * q〜0〜*は、入力が処理される初期状態です（q〜0〜∈Q）。
Mealyマシンの状態テーブルは以下に示されています-
現状
次の状態
入力= 0
入力= 1
状態
出力
状態
出力
→ a
b
x1
c
x1
b
b
x2
d
x3
c
d
x3
c
x1
d
d
x3
d
x2
上記のMealy Machineの状態図は-
ムーア機
ムーアマシンは、出力が現在の状態のみに依存するFSMです。
Mooreマシンは、6タプル（Q、∑、O、δ、X、q〜0〜）で記述できます。
- Q は有限状態のセットです。
- ∑ は、入力アルファベットと呼ばれる有限の記号セットです。
- O は、出力アルファベットと呼ばれる記号の有限セットです。
- *δ*は入力遷移関数です。δ：Q×input→Q
- X は出力遷移関数です。X：Q→O
- * q〜0〜*は、入力が処理される初期状態です（q〜0〜∈Q）。
ムーア機械の状態表を以下に示します-
現状
次の状態
出力
入力= 0
入力= 1
→ a
b
c
x2
b
b
d
x1
c
c
d
x2
d
d
d
x3
上記のムーア機械の状態図は-
Mealy Machine vs. ムーア機
次の表は、MealyマシンとMooreマシンを区別するポイントを強調しています。
| Mealy Machine | Moore Machine |
|---|---|
| Output depends both upon the present state and the present input | Output depends only upon the present state. |
| Generally, it has fewer states than Moore Machine. | Generally, it has more states than Mealy Machine. |
| The value of the output function is a function of the transitions and the changes, when the input logic on the present state is done. | The value of the output function is a function of the current state and the changes at the clock edges, whenever state changes occur. |
| Mealy machines react faster to inputs. They generally react in the same clock cycle. | In Moore machines, more logic is required to decode the outputs resulting in more circuit delays. They generally react one clock cycle later. |
ムーア機からミーリー機
アルゴリズム4
入力-ムーア機械
出力-Mealy Machine
- ステップ1 *-空のMealy Machine遷移テーブル形式を使用します。
- ステップ2 *-すべてのMoore Machineの遷移状態をこのテーブル形式にコピーします。
- ステップ3 *-現在の状態と対応するMoore Machine状態テーブルの出力を確認します。状態Q〜i〜の出力がmの場合、Q〜i〜が次の状態で現れる場所であればどこでも、それをMealy Machine状態テーブルの出力列にコピーします。
例
私たちは次のムーアマシンを考えてみましょう-
現状
次の状態
出力
a = 0
a = 1
→ a
d
b
1
b
a
d
0
c
c
c
0
d
b
a
1
次に、アルゴリズム4を適用してMealy Machineに変換します。
- ステップ1および2 *-
現状
次の状態
a = 0
a = 1
状態
出力
状態
出力
→ a
d
b
b
a
d
c
c
c
d
b
a
- ステップ3 *-
現状
次の状態
a = 0
a = 1
状態
出力
状態
出力
> a
d
1
b
0
b
a
1
d
1
c
c
0
c
0
d
b
0
a
1
MealyマシンからMooreマシン
アルゴリズム5
入力-Mealy Machine
出力-ムーア機械
- ステップ1 *-Mealyマシンの状態テーブルで利用可能な各状態（Q〜i〜）の異なる出力の数を計算します。
ステップ2 *-Qiのすべての出力が同じ場合、状態Q〜i〜をコピーします。 n個の個別の出力がある場合、Q〜i〜をQ〜in〜としてn個の状態に分割します。ここで、 *n = 0、1、2 …….
- ステップ3 *-初期状態の出力が1の場合、出力に0を与える新しい初期状態を最初に挿入します。
例
私たちは次のミーリーマシンを考えてみましょう-
現状
次の状態
a = 0
a = 1
次の状態
出力
次の状態
出力
→ a
d
0
b
1
b
a
1
d
0
c
c
1
c
0
d
b
0
a
1
ここでは、状態「a」と「d」はそれぞれ1と0の出力のみを提供するため、状態「a」と「d」を保持します。 ただし、「b」と「c」は異なる出力（1と0）を生成します。 したがって、 b を* b〜0〜、b〜1〜に分割し、 *c を* c〜0〜、c〜1〜*に分割します。
現状
次の状態
出力
a = 0
a = 1
→ a
d
b1
1
b0
a
d
0
b1
a
d
1
c0
c1
C0
0
c1
c1
C0
1
d
b0
a
0
