マルコフアルゴリズム

提供: miniwiki
移動先:案内、検索

マルコフアルゴリズム（英: Markov algorithm）とは、記号の文字列に対して一種の文法的規則を適用していく文字列書き換え系である。マルコフアルゴリズムはチューリング完全であることがわかっており、計算の汎用モデルとして使え、任意の数式を単純な記法で表現できる。

Refal はマルコフアルゴリズムに基づいたプログラミング言語である。考案者のアンドレイ・マルコフは、マルコフ連鎖のアンドレイ・マルコフの同名の息子である。

アルゴリズム

  1. 規則を上から順にチェックし、矢印の左辺の文字列が記号文字列にないか調べる。
  2. 1つも見つからない場合、アルゴリズムの実行を停止する。
  3. 1つ以上見つかった場合、記号文字列の中でも最も左端に近い部分にマッチした規則を適用し、矢印の右辺の文字列と置換する。
  4. 適用した規則が停止規則（terminating rule）であった場合、アルゴリズムを停止する。
  5. ステップ1に戻って繰り返す。

例

以下の例は、マルコフアルゴリズムの基本操作を示したものである。

規則

  1. "A" -> "apple"
  2. "B" -> "bag"
  3. "S" -> "shop"
  4. "T" -> "the"
  5. "the shop" -> "my brother"
  6. "a never used" -> ."terminating rule"

記号文字列

"I bought a B of As from T S."

実行

このアルゴリズムが上記の例に適用された場合、記号文字列は次のように変化する。

  1. "I bought a B of apples from T S."
  2. "I bought a bag of apples from T S."
  3. "I bought a bag of apples from T shop."
  4. "I bought a bag of apples from the shop."
  5. "I bought a bag of apples from my brother."

そうして、このアルゴリズムは停止する。

別の例

次の例はやや興味深い例である。この規則群を適用すると、ある非負整数を2進法で書いたものが、その数の縦棒に置換される。例えば、101 は 5 本の縦棒に書き換えられる（ICの74138といったデコーダ・デマルチプレクサのような働きと言える）。

規則

  1. "|0" -> "0||"
  2. "1" -> "0|"
  3. "0" -> ""

記号文字列

"101"

実行

このアルゴリズムが上記の例に適用された場合、次のように変化して停止する。

  1. "0|01"
  2. "00||1"
  3. "00||0|"
  4. "00|0|||"
  5. "000|||||"
  6. "00|||||"
  7. "0|||||"
  8. "|||||"

参考文献

  • Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191-206.
  • Andrey Andreevich Markov (1903-1979) 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=マルコフアルゴリズム&oldid=112409」から取得