# Markov algorithm simulator (Python)

**Other implementations**: Ocaml |**Python**

The following is an implementation of a Markov Algorithm system written in Python.

<<markov.py>>=Markov

We will be using functions from the *string* module:

<<Markov>>=importstring

A Markov algorithm is a string rewriting system consisting of rewrite rules. Each rule is a triple consisting of the word to match, the word to use as a replacement and a boolean flag. If the flag is true then the rule is a halting rule.

The successor algorithm is encoded as a list of rules.

<<Markov>>=successor = [("aL", "La", False), ("a0", "0a", False), ("a" , "b" , False), ("Lb", "b0", False), ("0b", "L" , True ), ("b" , "L" , True ), ("" , "a" , False)]

The *contains* function returns true if the second argument is a
substring of the first argument.

<<Markov>>=defcontains(s, sub):returns.find(sub) != -1

The *find_rule* function takes a list of *rules* and a *word* and returns
the first *rule* that matches. The *contains* function defined above is used
to test for the match. If no matching rule is found then the exception *ValueError* is raised.

<<Markov>>=deffind_rule(a, w):try:returnfilter(lambda(l,r,b): contains(w, l), a)[0]exceptIndexError:raiseValueError, "not found"

The *apply_rule* function applies a single *rule* to a *word*. This function
searches the *word* until it matches the left side of the rule. Once the match
is found the text is replaced with the right side of the rule and the resulting
*word* is returned.

<<Markov>>=defapply_rule((l,r,b), s):returns.replace(l, r, 1)

The *apply_alg* function takes a list of *rules* and a *word* and applies the
first matching *rule*. The *find_rule*
function is used to find the first matching rule then the *apply_rule*
function is used to apply the rule. A pair is returned containing the resulting
*word* and a bool flag, the flag is true if the rule that was applied was a halting
rule. *ValueError* is raised if no rule matches.

<<Markov>>=defapply_alg(a, w): l,r,b = r = find_rule(a, w)returnapply_rule(r, w), b

The *run* function applies the Markov algorithm continuously until either
a halting rule is matched or no rule is matched.
The word sequence that results from applying the algorithm is returned.
This function calls itself recursively with the result of the previous call
to *apply_alg*.

<<Markov>>=defrun(a, w): result = [] flag = False # whether Halting rule was appliedtry:whilenotflag: # Normal rule was applied result.append(w) w, flag = apply_alg(a, w) # apply a rule result.append(w)exceptValueError: # No rule was appliedpassreturnresult

Example:

>>> run(successor, "L0LL") ['L0LL', 'aL0LL', 'La0LL', 'L0aLL', 'L0LaL', 'L0LLa', 'L0LLb', 'L0Lb0', 'L0b00', 'LL00']

Download code |