Mostrar código-fonte de Operações em cadeias de caracteres

{{Não enciclopédico|data=fevereiro de 2015}}

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

==Concatenação==
{{Artigo principal|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_formal|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''<sub>''a''</sub> onde ''L''<sub>''a''</sub> ⊆ Δ<sup>[[Fecho de Kleene|*]]</sup> é 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 <ref>Hopcroft, Ullman (1979), Sect.3.2, p.60</ref>

:<math>f(L)=\bigcup_{s\in L} f(s)</math>

[[Linguagem_regular| 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.<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60</ref>
Similarmente, [[linguagem livre de contexto|linguagens livres de contexto]] são fechadas sobre substituição de cadeia.<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131</ref><ref group=note>Contudo toda linguagem regular é também livre de contexto, o primeiro teorema não é implicado pelo segundo, uma vez que o primeiro retorna um resultado modelado para linguagens regulares.</ref>

Um simples exemplo é uma conversão ''f''<sub>uc</sub>(.) à forma maiúscula, que pode ser definida e.g. como a seguir:

{| class="wikitable"
|-
! letter !! mapped to language !! remark
|-
! ''x'' !! ''f''<sub>uc</sub>(''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''<sub>uc</sub> para cadeias, temos e.g.
* ''f''<sub>uc</sub>(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
* ''f''<sub>uc</sub>(‹u2›) = {‹U} ⋅ {ε} = {‹U›}, and
* ''f''<sub>uc</sub>(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.
Para a extensão de ''f''<sub>uc</sub> para linguagens, temos e.g.
* ''f''<sub>uc</sub>({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.
Para a extensão de ''f''<sub>uc</sub> para cadeias, temos e.g.
* ''f''<sub>uc</sub>(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
* ''f''<sub>uc</sub>(‹u2›) = {‹U} ⋅ {ε} = {‹U›}, e
* ''f''<sub>uc</sub>(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.
Para a extensão de ''f''<sub>uc</sub> para linguagens, temos e.g.
* ''f''<sub>uc</sub>({ ‹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 [[Linguagem_formal|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''.<ref group=note name="singleton sets">Formalmente, um homomofismo retorna uma linguagem que consiste em apenas uma cadeia, i.e. ''f''(''a'') = {''s''}.</ref><ref>Hopcroft, Ullman (1979), Sect.3.2, p.60-61</ref>

Homomofismos de cadeias são mofismos [[monoide]]s 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''<sup>−1</sup>(''s'') = { ''w'' | ''f''(''w'')=''s'' }

enquanto que a imagem homomorfica invertida de uma linguagem ''L'' é definida como

:''f''<sup>−1</sup>(''L'') = { ''s'' | ''f''(''s'') ∈ ''L'' }

No geral, ''f''(''f''<sup>−1</sup>(''L'')) ≠ ''L'', enquanto não há

:''f''(''f''<sup>−1</sup>(''L'')) ⊆ ''L''

e

:''L'' ⊆ ''f''<sup>−1</sup>(''f''(''L''))

para cada linguagem ''L''.

A classe de linguagens regulares é fechada sobre homomorfismos e homomorfismos invertidos.<ref>Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61</ref>
Similarmente, as gramáticas livre-de-contexto são fechadas sobre homomorfismos<ref group=note>Isto segue da conjectura de substituição de cadeias sobre substituições arbitrarias.</ref> e homomorfismos invertidos.<ref>Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132</ref>

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''<sub>uc</sub> pode também ser obtido ao definir similar à substituição de cadeia: ''g''<sub>uc</sub>(‹a›) = ‹A›, ..., ''g''<sub>uc</sub>(‹0›) = ε, mas deixando ''g''<sub>uc</sub> undefinido em caracteres de pontuação.

Exemplos de imagens homomorficas invertidas são
* ''g''<sub>uc</sub><sup>−1</sup>({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since ''g''<sub>uc</sub>(‹sss›) = ''g''<sub>uc</sub>(‹sß›) = ''g''<sub>uc</sub>(‹ßs›) = ‹SSS›, and
*''g''<sub>uc</sub><sup>−1</sup>({ ‹A›, ‹bb› }) = { ‹a› }, since ''g''<sub>uc</sub>(‹a›) = ‹A›, enquanto ‹bb› não pode ser alcançado por ''g''<sub>uc</sub>.
Para a ultima language, ''g''<sub>uc</sub>(''g''<sub>uc</sub><sup>−1</sup>({ ‹A›, ‹bb› })) = ''g''<sub>uc</sub>({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }.
O homomorfismo ''g''<sub>uc</sub> não é ε-livre, uma vez que mapeia e.g. ‹0› para ε.

==Projeção de cadeia==
Se ''s'' é uma cadeia, e <math>\Sigma</math> é um alfabeto, a '''projeção de cadeia''' de ''s'' é a cadeia que resulta em remover todas as letras que não estão em <math>\Sigma</math>. É escrito como <math>\pi_\Sigma(s)\,</math>. É formalmente definido da remoção de letras do lado da mão direita.

:<math>\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}</math>

Aqui <math>\varepsilon</math> 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

:<math>\pi_\Sigma (L)=\{\pi_\Sigma(s) \vert s\in L \}</math>

==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 <math>s/a</math>. Se a cadeia naõ tem ''a'' no lado referente a mão direita, o resultado é a cadeia vazia. Assim:

:<math>(sa)/ b = \begin{cases}
s & \mbox{if } a=b \\
\varepsilon & \mbox{if } a \ne b
\end{cases}</math>

O quociente de uma cadeia vazia é pode ser obtido:

:<math>\varepsilon / a = \varepsilon</math>

De modo similar, dado um subconjunto <math>S\subset M</math> de um monoide <math>M</math>, pode-se definir o subconjunto quociente como

:<math>S/a=\{s\in M \vert sa\in S\}</math>

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 <math>S\subset M</math> de um monoide <math>M</math> define uma relação de equivalencia, chamada de '''relação sintática à direita''' de ''S''. É dada por

:<math>\sim_S \;\,=\, \{(s,t)\in M\times M \vert S/s = S/t \}</math>

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

:<math>\{S/m \vert m\in M\}</math>

é 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 <math>s\div a</math> e é recursivamente definido como

:<math>(sa)\div b = \begin{cases}
s & \mbox{if } a=b \\
(s\div b)a & \mbox{if } a \ne b
\end{cases}</math>

A cadeia vazia é sempre cancelável:

:<math>\varepsilon \div a = \varepsilon</math>

Claramente, cancelamento à direita e projeção comutam:

:<math>\pi_\Sigma(s)\div a = \pi_\Sigma(s \div a )</math>

==Prefixos==
O '''prefixo de uma cadeia''' é um conjunto de todos os prefixos de uma cadeia, com relação à dada linguagem:

:<math>\operatorname{Pref}_L(s) = \{t \vert s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^*\}</math>

here <math>s\in L</math>.
aqui <math>s\in L</math>.

A '''conjectura de prefixo de uma linguagem''' é

:<math>\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\}</math>

'''Exemplo:''' <br>
<math>L=\left\{abc\right\}\mbox{ then } \operatorname{Pref}(L)=\left\{\varepsilon, a, ab, abc\right\}</math>

Uma linguagem é chamada '''fechada em prefixo''' se <math>\operatorname{Pref} (L) = L</math>.

O operador de conjectura de prefixo é idempotente:

:<math>\operatorname{Pref} (\operatorname{Pref} (L)) =\operatorname{Pref} (L)</math>

A '''relação de prefixo''' é a relação binária <math>\sqsubseteq</math> tal que <math>s\sqsubseteq t </math> se e somente se <math>s \in \operatorname{Pref}_L(t)</math>. Essa relação é um exemplo particular de uma ordem de prefixo.

== Ver também ==
* [[Cadeia de caracteres]]

==Notas==
{{reflist|group=note}}

== Referências ==

* {{citar livro|primeiro1 =John E. |último1 =Hopcroft |primeiro2 =Jeffrey D. |último2 =Ullman |título=Introduction to Automata Theory, Languages and Computation |publicado=Addison-Wesley Publishing |local=Reading, Massachusetts |ano=1979 | isbn=0-201-02988-X | zbl=0426.68001 }} ''(See chapter 3.)''
{{reflist}}

[[Categoria:Linguagens formais]]