Sistema de cadeia reescrito
# Sistema de cadeia reescrito

Um sistema de cadeia reescrito é um sistema de substituição usado para criar cadeias lógias a partir de determinadas regras de reescrita.

## Bases de equivalência para sistemas de cadeias reescritos

Certas formas básicas que formam o sistema de cadeias reescritas são essencialmente equivalentes ao sistema de termos reescritos Supomos que temos cadeias lógicas sobre algum alfabeto A, e apenas damos uma lista de transformações com regras em cadeia lógica sob a forma: $x_{0}x_{1}\cdots x_{n}\rightarrow y_{0}y_{1}\cdots y_{m},\quad x_{i},y_{i}\in A$; isso indica que qualquer cadeia X $_0$x$_1$...x$_n$ é recolocada com Y $_0$y$_1$...y$_m$.
Podemos reformular o sistema por um termo de um sistema reescrito—as regras de transformação podem se tornar : $x_{0}(x_{1}(\cdots (x_{n}(x)))\cdots )\rightarrow y_{0}(y_{1}(\cdots (y_{m}(x))\cdots ),$ onde cada X x$_i$ e y$_i$ constitui os símbolos de funções em um termo de um sistema reescrito.
Cadeias são esses termos de sistemas reescritos que fazem crescer o termo.

## Exemplos

exemplos de modelos computacionais baseados em determinadas cadeias reescritas incluem o algoritmo de Markov, sistemas pós-canônicoss (e.g., sistemas Tags), uma variedade de formas gramaticais, nos L-systems (os últimos se conduzindo a certos tipos de fractais, como o conjunto de Cantor e a Esponja de Menger).