Cadeia inversa

Seja a cadeia

${\displaystyle w=(w_{0},w_{1},\cdots ,w_{n-1},w_{n})\,\!}$

então

${\displaystyle w^{\mathbf {R} }=(w_{n},w_{n-1},\cdots ,w_{1},w_{0})\,\!}$

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

• O comprimento de uma cadeia é igual ao da sua cadeia inversa:

${\displaystyle |w|=|w^{\mathbf {R} }|}$

• O inverso da cadeia inversa de uma cadeia é igual a própria cadeia:

${\displaystyle (w^{\mathbf {R} })^{\mathbf {R} }=w}$

• A cadeia inversa da cadeia vazia é a própria cadeia vazia:

${\displaystyle {\varepsilon \,}^{\mathbf {R} }=\varepsilon \,}$

• Uma cadeia w é igual a sua inversa se, e somente se, w é um palíndromo:

${\displaystyle w=w^{\mathbf {R} }=(w_{0},w_{1},\cdots ,w_{n-1},w_{n})\Longleftrightarrow w_{i}=w_{n-i}\qquad \forall w_{i}\in \left\{w_{0},\cdots ,w_{n}\right\}}$

• Cadeia de caracteres