Sistema de cadeia reescrito

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Reescrita)
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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_0x_1\cdots x_n \rightarrow y_0y_1\cdots y_m,\quad x_i, y_i \in A; isso indica que qualquer cadeia X 0x1...xn é recolocada com Y 0y1...ym.

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 xi e yi 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[editar | editar código-fonte]

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).

Ver também[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.