马尔可夫算法
马尔可夫算法是使用类似形式文法的规则在符号串上操作的字符串重写系统。马尔可夫算法被证明是图灵完全的,这意味着它们适合作为一般的计算模型,并可以用它的简单概念表示任何数学表达式。
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 B of apples from T S."
- "I bought a bag of apples from T S."
- "I bought a bag of apples from T shop."
- "I bought a bag of apples from the shop."
- "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.
外部链接编辑
🔥 Top keywords: Baike: 首页Special:搜索毛泽东家族榮耀之繼承者天之驕女鐵拳英雄九龍城寨之圍城黃循財背着善宰跑篠崎泫妮妃雅新生 (网络剧)劉偉健斯洛伐克习近平劉俊謙 (香港)李显龙歌手2024佛誕淚之女王2024年泰國羽球公開賽新加坡總理邊佑錫新加坡Energy (組合)庆余年九龍寨城六四事件家族榮耀金智媛彌助菲律宾胖猫跳江事件劉寶傑DAY6林峯張文傑李光耀神耆小子張鳳妮黃世聰Seventeen (組合)维基百科願榮光歸香港中華民國鬼滅之刃 柱訓練篇2024年英雄联盟季中邀请赛中华人民共和国TripleS金秀賢 (男演員)罗伯特·菲佐井柏然2024年世界女排联赛黃偉哲怪獸8號佘詩曼Foodpanda金惠奫新加坡总统香緹·摩爾于北辰 (1968年)王嘉爾笑看風雲排球少年!!角色列表林飛帆郭葦昀馴鹿寶貝翁靜晶猩球崛起:王國誕生ILLIT尼古拉·約基奇春色寄情人周殷廷鬼滅之刃排球少年!!吳釗燮逆天奇案2不夠善良的我們BABYMONSTER李正皓尚达曼BOYNEXTDOOR胡子彤IVE (組合)陳靜 (香港)香港吴作栋黃道十二宮凡希亚·奥伊亚胡宇威長洲太平清醮張員瑛搜查班長1958伍允龍习明泽黄岩岛賴清德偶然遇見的你虽然不是英雄