このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 順序機械 へ行く。

*目次 [#mb8b9d1b]

#contents


*順序機械 [#q90a2008]

 ''順序機械''は記憶のある回路や機械を抽象化したもので、次の性質を持つ記号処理機械である。

-入力記号によって変化し過去の入力の状況を記憶する内部状態を持つ。
-入力と内部状態に依存して出力記号が決まる。

 入力とそのときの内部状態に依存して内部状態を変わることを''状態遷移''という。特に、状態が有限個しかない順序機械は''有限状態機械''とという。これは順序機械の中で実用上重要である。

例:順序論理回路のもっとも簡単なものとしては[[フリップフロップ]]が挙げられる。


*状態遷移図 [#u16c0487]

 ''状態遷移図''とは、状態が入力によってどのように遷移するのかを[[有向グラフ]]によって図示したものである。状態を点に対応させて、状態名をラベルとし、有向辺には入力記号を対応させて、辺ラベルとした表現である。

 出力はそのときの状態と入力で決まるなら辺ラベルの一部として表現させる。これを''ミーリー(Mealy)機械''という。一方、遷移先の状態で決まるなら点ラベルの一部として表現させる。これを''ムーア(Moore)機械''という。

例1:ミーリー機械の例

-[[Dフリップフロップ]]
--1入力1出力のフリップフロップで、入力dの値が変化すると変化前の値を出力する遅れ(delay)素子の役割をする。

例2:ムーア機械の例

-[[RSフリップフロップ]]
--2入力1出力(見かけは2出力)のフリップフロップで、出力は遷移先の状態と同じである。



 順序機械の動作を記述するには''初期状態''を指定する必要がある。


*状態遷移関数と出力関数 [#w054f052]

-Σ:入力記号の集合(入力アルファベット)
-Q:内部状態

 このとき、状態と入力記号から次の状態が決まる状態遷移を写像δ:Q×Σ→Qとみなしたとき、δを''状態遷移関数''という。遷移関数を関数表として表したものが''状態遷移表''である。

Γ:出力記号の集合(出力アルファベット)

 出力はそのときの状態と入力記号に依存する。それを関数とみたものを''出力関数''といい、γで表す。γはQ×Σ→Γという写像を持つ。

例:

-[[Dフリップフロップの状態遷移表と出力関数表:http://akademeia.info/index.php?D%A5%D5%A5%EA%A5%C3%A5%D7%A5%D5%A5%ED%A5%C3%A5%D7#o184e835]]
-[[RSフリップフロップの状態遷移表と出力関数表:]]
-[[Tフリップフロップの状態遷移表と出力関数表:]]
-[[JKフリップフロップの状態遷移表と出力関数表:]]



*参考文献 [#id9d605c]

-『形式言語と有限オートマトン入門』