Markov algorithm for string rewriting

The Markov algorithm is a Turing complete string rewriting system. A table of rules is used to translate occurrences of symbols in an input string indefinitely until no more rules apply.

Not to be confused with the Markov Chain text generator :)

The default example evaluates nested parenthetical binary addition.

Note: terminating rules (usually marked with a dot ".") are not implemented.

Other examples:

"A" -> "apple"
"B" -> "bag"
"S" -> "shop"
"T" -> "the"
"the shop" -> "my brother"

Example input string: "I bought a B of As from T S."