É possível derivar uma string nesse sistema de reescrita?

Sistema de reescrita é um conjunto de regras na forma de . Se aplicarmos essa regra a uma string , substituiremos qualquer substring em por um substring e vice-versa. $A \leftrightarrow B$ $w$ $A$ $w$ $B$

Dada uma sequência inicial podemos derivar no sistema com as seguintes regras: $AAABB$ $BAAB$

$A \leftrightarrow BA$
$BABA \leftrightarrow AABB$
$AAA \leftrightarrow AB$
$BA \leftrightarrow AB$

Existe um algoritmo geral para isso?

computability term-rewriting Daniil
fonte

Eu gostaria que você pudesse adicionar mais tags a esta pergunta ou alterar o conjunto de regras para torná-la mais legal.

Daniil

@JD Eu acho que, em geral, este problema reescrevendo não pode ser resolvido, porque você pode modelar máquina de Turing com o sistema tal reescrever e problema derivação == problema da parada na TM

Daniil

@ Ah ah, isso faz sentido, eu deveria ler mais sobre isso, obrigado!

Daniil

@Daniil e futuros leitores: O problema indecidível usado é o problema de correspondência posterior .

Jmad

Essa é essencialmente a idéia de algoritmo de Markov.

vonbrand

Respostas:

Observe que a paridade do número de s não muda. Como uma string contém um número ímpar e a outra par, elas não são alcançáveis. $A$ $A$

Acredito em geral (para um conjunto arbitrário de regras, não seu exemplo específico), é provável que seja um problema indecidível. Se as transformações são unidirecionais (ou seja, regras no formato ), é assim, por exemplo, consulte: Sistema de etiquetas . $A \to BA$

Aryabhata
fonte

Sim, IIRC, é indecidível porque você pode modelar uma TM com um conjunto específico de regras de reescrita.

Daniil