马尔可夫算法

马尔可夫算法是使用类似形式文法的规则在符号串上操作的字符串重写系统。马尔可夫算法被证明是图灵完全的，这意味着它们适合作为一般的计算模型，并可以用它的简单概念表示任何数学表达式。

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

算法接着就终止了。