馬爾可夫算法

馬爾可夫算法是使用類似形式文法的規則在符號串上操作的字符串重寫系統。馬爾可夫算法被證明是圖靈完全的，這意味着它們適合作為一般的計算模型，並可以用它的簡單概念表示任何數學表達式。

Refal是基於馬爾可夫算法的程式語言。

算法

1. 自頂向下依次檢查規則，看是否能在符號串中找到任何在箭頭左邊的字符串。
2. 如果沒有找到，停止執行算法。
3. 如果找到一個或多個，把符號串中的最左匹配的文字替換為在第一個相應規則的箭頭右邊的字符串。
4. 返回步驟1並繼續。（如果應用的規則是終止規則，則停止執行算法。）

例子

下列例子展示了馬爾可夫算法的基本操作。

規則

1. "A" -> "apple"
2. "B" -> "bag"
3. "S" -> "shop"
4. "T" -> "the"
5. "the shop" -> "my brother"
6. "從不使用的" -> ."終止規則"

符號串

"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."

算法接着就終止了。

引用

• 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.

外部連結

• Markov algorithm interpreter （頁面存檔備份，存於互聯網檔案館）
• Markov algorithm interpreter
• Markov algorithm interpreter (Applet) （頁面存檔備份，存於互聯網檔案館）