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

Ver 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, 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	fuc(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⁻¹(s) = { w | f(w)=s }

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

f⁻¹(L) = { s | f(s) ∈ L }

No geral, f(f⁻¹(L)) ≠ L, enquanto não há

f(f⁻¹(L)) ⊆ L

e

L ⊆ f⁻¹(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⁻¹({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since g_uc(‹sss›) = g_uc(‹sß›) = g_uc(‹ßs›) = ‹SSS›, and
• g_uc⁻¹({ ‹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⁻¹({ ‹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.

Ver também

• Cadeia de caracteres

Referências

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages and Computation. Reading, Massachusetts: Addison-Wesley Publishing. ISBN 0-201-02988-X. Zbl 0426.68001  (See chapter 3.)