# Operações em cadeias de caracteres

Em ciência da computação e nas linguagens formais é comum o uso de uma variedade de funções que operam sobre cadeias de caracteres com o intuito de transformá-las em variações bem definidas com base em sua estrutura original.

## Concatenação

É a operação que une uma cadeia de caracteres a outra cadeia de caracteres, formando uma nova cadeia contendo os caracteres da primeira seguidos pelos caracteres da segunda. A concatenação de duas cadeias s e t é usualmente denotado por s · t ou abreviado como st. Concatenar uma cadeia qualquer com uma cadeia vazia 𝜀 não altera a cadeia original, assim s · 𝜀 = s = 𝜀 · s. A concatenação de cadeias de caraceres é associativa, mas não é comutativa, portanto, s · (t · u) = (s · t) · u, mas s · t ≠ t · s.

## Substituição de cadeia

Seja L uma linguagem, e seja Σ seu alfabeto. Uma substituição de cadeia ou simplesmente uma substituição é um mapeamento f que mapeia letras em Σ para linguagens (possivelmente em um alfabeto diferente). Assim, por exemplo, dada uma letra a ∈ Σ, existe f(a)=L$_a$ onde L$_a$ ⊆ Δ é alguma linguagem cujo alfabeto é Δ. Esse mapeamente pode ser estendido para cadeias como:
    f(ε)=ε
para a cadeia vazia ε, e
    f(sa)=f(s)f(a)
para uma cadeia s ∈ L. Substituições de cadeias podem ser estendidas a linguagens inteias como
    $f(L)=\bigcup _{s\in L}f(s)$
Linguagens regulares são fechadas sobre substituição de cadeia. Isto é, se cada letra de uma linguagem regular é substituida por uma outra linguagem regular, o resultado é ainda a linguagem regular. Similarmente, linguagens livres de contexto são fechadas sobre substituição de cadeia.
Um simples exemplo é uma conversão f$_{uc}$(.) à forma maiúscula, que pode ser definida e.g. como a seguir:
| letter | mapped to language | remark |
| x | f$_{uc}$(x) | |
| ‹a› | { ‹A› } | map lower-case char to corresponding upper-case char |
| ‹A› | { ‹A› } | map upper-case char to itself |
| ‹ß› | { ‹SS› } | no upper-case char available, map to two-char cadeia |
| ‹0› | { ε } | map digit to empty cadeia |
| ‹!› | { } | forbid punctuation, map to empty language |
| ... | | similar for other chars |
Para a extensão de f$_{uc}$ para cadeias, temos e.g.
* f$_{uc}$(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
* f$_{uc}$(‹u2›) = {‹U} ⋅ {ε} = {‹U›}, and
* f$_{uc}$(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ =.
Para a extensão de f$_{uc}$ para linguagens, temos e.g.
* f$_{uc}$({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.
Para a extensão de f$_{uc}$ para cadeias, temos e.g.
* f$_{uc}$(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
* f$_{uc}$(‹u2›) = {‹U} ⋅ {ε} = {‹U›}, e
* f$_{uc}$(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ =.
Para a extensão de f$_{uc}$ para linguagens, temos e.g.
* f$_{uc}$({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.
Um outro exemplo é a conversão de uma cadeia ASC codificada.

## Homomorfismo de cadeia

Um homomorfismo de cadeia (comumente referido como simplesmente homomorfismo em teoria de linguagens formais é a substituição de cadeia tal que cada letra é substituída por uma cadeia unitária. Isto é, f(a)-s, onde s é uma cadeia, para cada letra a.
Homomofismos de cadeias são mofismos monoides no monoide livre, preservando a operação binaria de concatenação de cadeia. Dada uma linguagem L, o conjunto f(L) é chamado imagem homomorfica de L. A imagem homomorfica invertida de uma cadeia s é definida como
    f$^{−1}$(s) = { w | f(w)=s }
enquanto que a imagem homomorfica invertida de uma linguagem L é definida como
    f$^{−1}$(L) = { s | f(s) ∈ L }
No geral, f(f$^{−1}$(L)) ≠ L, enquanto não há
    f(f$^{−1}$(L)) ⊆ L
e
    L ⊆ f$^{−1}$(f(L))
para cada linguagem L.
A classe de linguagens regulares é fechada sobre homomorfismos e homomorfismos invertidos. Similarmente, as gramáticas livre-de-contexto são fechadas sobre homomorfismos e homomorfismos invertidos.
Um homomorfismo de cadeia é dito ε-livre (ou e-livre) se f(a) ≠ ε para todo a no alfabeto Σ. Simples cifras de substituição de única letra são exemplos de homomorfismos de cadeia e-livres.
Um homomorfismo de cadeia exemplo g$_{uc}$ pode também ser obtido ao definir similar à substituição de cadeia: g$_{uc}$(‹a›) = ‹A›, ..., g$_{uc}$(‹0›) = ε, mas deixando g$_{uc}$ undefinido em caracteres de pontuação.
Exemplos de imagens homomorficas invertidas são
* g$_{uc}$$^{−1}$({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since g$_{uc}$(‹sss›) = g$_{uc}$(‹sß›) = g$_{uc}$(‹ßs›) = ‹SSS›, and
* g$_{uc}$$^{−1}$({ ‹A›, ‹bb› }) = { ‹a› }, since g$_{uc}$(‹a›) = ‹A›, enquanto ‹bb› não pode ser alcançado por g$_{uc}$.
Para a ultima language, g$_{uc}$(g$_{uc}$$^{−1}$({ ‹A›, ‹bb› })) = g$_{uc}$({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. O homomorfismo g$_{uc}$ não é ε-livre, uma vez que mapeia e.g. ‹0› para ε.

## Projeção de cadeia

Se s é uma cadeia, e $\Sigma$ é um alfabeto, a projeção de cadeia de s é a cadeia que resulta em remover todas as letras que não estão em $\Sigma$. É escrito como $\pi _{\Sigma }(s)\,$. É formalmente definido da remoção de letras do lado da mão direita.
    $\pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty cadeia}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}$
Aqui $\varepsilon$ denota a cadeia vazia. A projeção de uma cadeia é essencial tal qual a projeção em algebra relacional.
Projeção de cadeia pode ser promovido a projeção de uma linguagem. Dada uma linguagem formal L, sua projeção é dada por
    $\pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\vert s\in L\}$

## Quociente à direita

O quociente à direita de uma letra a de uma cadeia s é a truncação da letra a na cadeia s, do lado referente a mão direita. É denotado como $s/a$. Se a cadeia naõ tem a no lado referente a mão direita, o resultado é a cadeia vazia. Assim:
    $(sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}$
O quociente de uma cadeia vazia é pode ser obtido:
    $\varepsilon /a=\varepsilon$
De modo similar, dado um subconjunto $S\subset M$ de um monoide $M$, pode-se definir o subconjunto quociente como
    $S/a=\{s\in M\vert sa\in S\}$
Quocientes à esquerda podem ser definidos de maneira similar, com operações se colocando à esquerda de uma cadeia.

## Relação sintática

O quociente à direita de um subconjunto $S\subset M$ de um monoide $M$ define uma relação de equivalencia, chamada de relação sintática à direita de S. É dada por
    $\sim _{S}\;\,=\,\{(s,t)\in M\times M\vert S/s=S/t\}$
A relação é claramente de indice finito (tem um número finito de classes de equivalencia) se e somente se a família quocientes à direita é finida; isto é, se
    $\{S/m\vert m\in M\}$
é finito. Nesse caso, S é uma linguagem reconhecível, isto é, uma linguagem que pode ser reconhecida por um automato de estados finito. Isto é discutido em mais detalhes no artigo sobre monoides sintáticos.

## Cancelamento à direita

O cancelamento à direita de uma letra a de uma cadeia s é a remoção da primeira ocorrencia de uma letra a na cadeia s, começando pelo lado referente a mão direita. Isto é denotado como $s\div a$ e é recursivamente definido como
    $(sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}$
A cadeia vazia é sempre cancelável:
    $\varepsilon \div a=\varepsilon$
Claramente, cancelamento à direita e projeção comutam:
    $\pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)$

## Prefixos

O prefixo de uma cadeia é um conjunto de todos os prefixos de uma cadeia, com relação à dada linguagem:
    $\operatorname {Pref} _{L}(s)=\{t\vert s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}$
here $s\in L$. aqui $s\in L$.
A conjectura de prefixo de uma linguagem é
    $\operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\vert s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}$
Exemplo:
$L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}$
Uma linguagem é chamada fechada em prefixo se $\operatorname {Pref} (L)=L$.
O operador de conjectura de prefixo é idempotente:
    $\operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)$
A relação de prefixo é a relação binária $\sqsubseteq$ tal que $s\sqsubseteq t$ se e somente se $s\in \operatorname {Pref} _{L}(t)$. Essa relação é um exemplo particular de uma ordem de prefixo.