Sub Markov (rules As String, entrada As String, expected As String)
    Dim As String subs(), reps(), lines()
    Dim As String sub_, rep, li, res
    Dim As Integer i, k
    Dim As Integer start = 1, finish = 1

    While finish <= Len(rules)
        If Mid(rules, finish, 1) = Chr(10) Then
            Redim Preserve lines(Ubound(lines) + 1)
            lines(Ubound(lines)) = Mid(rules, start, finish - start)
            start = finish + 1
        End If
        finish += 1
    Wend
    For i = 0 To Ubound(lines)
        li = lines(i)
        If Len(li) > 0 And Asc(li, 1) <> Asc("#") Then
            k = Instr(li, " -> ")
            If k > 0 Then
                Redim Preserve subs(Ubound(subs) + 1)
                subs(Ubound(subs)) = Trim(Mid(li, 1, k - 1))
                Redim Preserve reps(Ubound(reps) + 1)
                reps(Ubound(reps)) = Trim(Mid(li, k + 4))
            End If
        End If
    Next i

    res = entrada
    Dim As Boolean term = False, found = False
    Do
        found = False
        For i = 0 To Ubound(subs)
            sub_ = subs(i)
            k = Instr(res, sub_)
            If k > 0 Then
                found = True
                rep = reps(i)
                If Len(rep) > 0 And Asc(rep, 1) = Asc(".") Then
                    rep = Mid(rep, 2)
                    term = True
                End If
                Mid(res, k, Len(sub_)) = rep
                Exit For
            End If
            If Not term Then Exit For
        Next i
        If Not term Or Not found Then Exit Do
    Loop
    Print """"; entrada;""""; ", "; """"; expected; """"; ", "; Iif(res = expected, "**ERROR**", "ok")
End Sub

Dim As String ruleset1 = _
"# This rules file is extracted from Wikipedia:" & _
"# http://en.wikipedia.org/wiki/Markov_Algorithm" & _
"A -> apple" & _
"B -> bag" & _
"S -> shop" & _
"T -> the" & _
"the shop -> my brother" & _
"a never used -> .terminating rule"
Markov(ruleset1,"I bought a B of As from T S.","I bought a bag of apples from my brother.")

Dim As String ruleset2 = _
"# Slightly modified from the rules on Wikipedia" & _
"A -> apple" & _
"B -> bag" & _
"S -> .shop" & _
"T -> the" & _
"the shop -> my brother" & _
"a never used -> .terminating rule"
Markov(ruleset2,"I bought a B of As from T S.","I bought a bag of apples from T shop.")

Dim As String ruleset3 = _
"# BNF Syntax testing rules" & _
"A -> apple" & _
"WWWW -> with" & _
"Bgage -> ->.*" & _
"B -> bag" & _
"->.* -> money" & _
"W -> WW" & _
"S -> .shop" & _
"T -> the" & _
"the shop -> my brother" & _
"a never used -> .terminating rule"""
Markov(ruleset3,"I bought a B of As W my Bgage from T S.","I bought a bag of apples with my money from T shop.")

Dim As String ruleset4 = _
"### Unary Multiplication Engine, for testing Markov Algorithm implementations" & _
"### By Donal Fellows." & _
"# Unary addition engine" & _
"_+1 -> _1+" & _
"1+1 -> 11+" & _
"# Pass for converting from the splitting of multiplication into ordinary" & _
"# addition" & _
"1! -> !1" & _
",! -> !+" & _
"_! -> _" & _
"# Unary multiplication by duplicating left side, right side times" & _
"1*1 -> x,@y" & _
"1x -> xX" & _
"X, -> 1,1" & _
"X1 -> 1X" & _
"_x -> _X" & _
",x -> ,X" & _
"y1 -> 1y" & _
"y_ -> _" & _
"# Next phase of applying" & _
"1@1 -> x,@y" & _
"1@_ -> @_" & _
",@_ -> !_" & _
"++ -> +" & _
"# Termination cleanup for addition" & _
"_1 -> 1" & _
"1+_ -> 1" & _
"_+_ -> "
Markov(ruleset4,"_1111*11111_","11111111111111111111")

Dim As String ruleset5 = _
"# Turing machine: three-state busy beaver" & _
"#" & _
"# state A, symbol 0 => write 1, move right, new state B" & _
"A0 -> 1B" & _
"# state A, symbol 1 => write 1, move left, new state C" & _
"0A1 -> C01" & _
"1A1 -> C11" & _
"# state B, symbol 0 => write 1, move left, new state A" & _
"0B0 -> A01" & _
"1B0 -> A11" & _
"# state B, symbol 1 => write 1, move right, new state B" & _
"B1 -> 1B" & _
"# state C, symbol 0 => write 1, move left, new state B" & _
"0C0 -> B01" & _
"1C0 -> B11" & _
"# state C, symbol 1 => write 1, move left, halt" & _
"0C1 -> H01" & _
"1C1 -> H11"
Markov(ruleset5,"000000A000000","00011H1111000")

Sleep