Cadeia inversa

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Na Ciência da Computação e na Teoria das linguagens formais, a cadeia inversa (ou cadeia reversa) de uma cadeia w, denominada wR, é a cadeia contendo os mesmos símbolos da cadeia original, na ordem inversa.

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

Seja a cadeia

então

Propriedades[editar | editar código-fonte]

Na Teoria das linguagens formais, cadeias inversas possuem algumas propriedades.

  • O comprimento de uma cadeia é igual ao da sua cadeia inversa:
  • O inverso da cadeia inversa de uma cadeia é igual a própria cadeia:
  • A cadeia inversa da cadeia vazia é a própria cadeia vazia:
  • Uma cadeia w é igual a sua inversa se, e somente se, w é um palíndromo:

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