マルコフアルゴリズム

マルコフアルゴリズム

マルコフアルゴリズムとは、記号から成る文字列に特定の文法ルールを適用し、文字列を段階的に書き換える方法です。このアルゴリズムは計算の汎用モデルとして利用され、任意の計算を表すことができる「チューリング完全」な性質を持っています。1951年にロシア人の数学者、アンドレイ・マルコフ・ジュニアによって初めて提唱され、1960年に英語に翻訳されました。元々は「normal algorithm」という名称で呼ばれていましたが、現在では一般に「マルコフアルゴリズム」として知られています。アンドレイ・マルコフ・ジュニアは、著名な確率過程である「マルコフ連鎖」の提唱者、アンドレイ・マルコフの息子です。

アルゴリズムの基本

マルコフアルゴリズムは、文字列の変換ルールを定義し、それに基づいて文字列を変換していきます。変換ルールは以下のように示されます：

• - パターン → 置換文字列（停止規則でない場合）
• - パターン → .置換文字列（停止規則の場合）。ここで、置換文字列の先頭にドット（.）を付けることが目印として用いられますが、このドットは置換後の文字列には含まれません。

アルゴリズムの実行は次の手順で行われます：
1. 変換ルールのリストを上から順にチェックし、パターンが文字列内に存在するか確認します。
2. パターンが見つからない場合、アルゴリズムは停止します。
3. パターンが見つかった場合は、最も左側に位置する部分に適用し、指定された置換文字列に書き換えます。
4. 停止規則が適用された場合は、アルゴリズムが終了します。処理が終了しない限り、1に戻り、作業を繰り返します。

実際の例

具体的な例として、以下の変換ルールを考えてみましょう：

• - A → apple
• - B → bag
• - S → shop
• - T → the
• - the shop → my brother
• - 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進法を縦棒に変換するルールを考えてみましょう：

• - 0 → 0|
• - 1 → 0|
• - 0 → ""（空文字列）

ここで、2進数「101」を処理すると、最終的に5本の縦棒に変換されることがわかります。

その他の応用

マルコフアルゴリズムは、計算理論において様々な応用があります。たとえば、チューリングマシンをマルコフアルゴリズムを通じて実装することも可能です。この際、チューリングマシンの状態遷移をマルコフアルゴリズムの変換規則として表現します。また、オペランドスタックを使用したスタックマシンの設計も可能で、さまざまな計算を記述できます。

参考文献

• - Caracciolo di Forino, A. (1968). String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, pp. 191-206.
• - Andrey Andreevich Markov (1960). The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.

外部リンク

• - Markov algorithm interpreter

もう一度検索