馬爾可夫算法

"I "I "I

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

算法

自頂向下依次檢查規則，看是否能在符號串中找到任何在箭頭左邊的字元串。
如果沒有找到，停止執行算法。
如果找到一個或多個，把符號串中的最左匹配的文字替換為在第一個相應規則的箭頭右邊的字元串。
如果套用的規則是終止規則，則停止執行算法。
返回步驟 1 並繼續。
[編輯] 例子
下列例子展示了馬爾可夫算法的基本操作。

規則

"A" -> "apple"
"B" -> "bag"
"S" -> "shop"
"T" -> "the"
"the shop" -> "my brother"
"從不使用的" -> ."終止規則"

符號串

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

執行

如果算法套用於上述例子，符號串將被以如下方式變更。
"I bought a bag of As from T S."
"I bought a bag of apples from T S."
"I bought a bag of apples from the S."
"I bought a bag of apples from the shop."
"I bought a bag of apples from my brother."
算法接著就終止了。