Usuário(a):Vitor.antero/algoritmo de Markov

Em teoria da computação, o algoritmo de Markov^[1], nomeado assim em homenagem à Andrei Markov, é um sistema de reescrita de cadeias que lança mão de regras de gramáticas para operar sobre cadeias de símbolos. Os algoritmos de Markov se mostraram Turing-completos, o que garante que eles provêm um modelo geral de computação e que podem representar qualquer expressão matemática.

Algoritmo[editar | editar código-fonte]

As Regras constituem-se de uma sequência de pares de cadeias, usualmente presentes na forma padrão->substituição. Algumas regras podem ser conclusivas.

Dada uma cadeia de entrada s:

Verifique as Regras com uma abordagem top-down, para verificar quantos padrões podem ser encontrados em s

Caso nenhum padrão seja encontrado, pare.

Use o primeiro de todos os padrões encontrados para substituir o matching mais à esquerda em s pela sua respectiva substituição.
Se a regra aplicada é conclusiva, pare.
Retorne ao passo 1 e continue.

Exemplo[editar | editar código-fonte]

Os seguintes exemplos mostram o operacional básico de um algoritmo de Markov.

Regras[editar | editar código-fonte]

“M” -> “maçã”
“B” -> “bolsa”
“L” -> “loja”
“da loja” -> “do meu irmão”

Cadeia de entrada[editar | editar código-fonte]

“Eu comprei uma B de Ms da L.”

Execução[editar | editar código-fonte]

Quando o algoritmo for aplicado sobre o exemplo acima, ele mostrará esta sequência de configurações:

“Eu comprei uma B de maçãs da L.”
“Eu comprei uma bolsa de maçãs da L.”
“Eu comprei uma bolsa de maçãs da loja.”
“Eu comprei uma bolsa de maçãs do meu irmão.”

Parando devido à falta de padrões encontrados.

Outro exemplo[editar | editar código-fonte]

Estas regras mostram um caso mais interessante. Elas transformam números binários em suas representações unárias. Neste exemplo, o número 101 será reescrito como 5 barras consecutivas.