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

Predefinição:Artigo principalÉ 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 $\mathrm{\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 $\mathrm{\Sigma }$. É escrito como ${\pi }_{\mathrm{\Sigma }}(s)$. É formalmente definido da remoção de letras do lado da mão direita.

${\pi }_{\mathrm{\Sigma }}(s)=\{\begin{array}{cc}\epsilon & \text{if }s=\epsilon \text{ the empty cadeia}\\ {\pi }_{\mathrm{\Sigma }}(t)& \text{if }s=ta\text{ and }a\notin \mathrm{\Sigma }\\ {\pi }_{\mathrm{\Sigma }}(t)a& \text{if }s=ta\text{ and }a\in \mathrm{\Sigma }\end{array}$

Aqui $\epsilon$ 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 }_{\mathrm{\Sigma }}(L)=\{{\pi }_{\mathrm{\Sigma }}(s)|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{array}{cc}s& \text{if }a=b\\ \epsilon & \text{if }a\ne b\end{array}$

O quociente de uma cadeia vazia é pode ser obtido:

$\epsilon /a=\epsilon$

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|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|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|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÷a$ e é recursivamente definido como

$(sa)÷b=\{\begin{array}{cc}s& \text{if }a=b\\ (s÷b)a& \text{if }a\ne b\end{array}$

A cadeia vazia é sempre cancelável:

$\epsilon ÷a=\epsilon$

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

${\pi }_{\mathrm{\Sigma }}(s)÷a={\pi }_{\mathrm{\Sigma }}(s÷a)$

Prefixos

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

${\mathrm{Pref}}_L(s)=\{t|s=tu\text{ for }t,u\in \mathrm{Alph}(L{)}^{*}\}$

here $s\in L$. aqui $s\in L$.

A conjectura de prefixo de uma linguagem é

$\mathrm{Pref}(L)=\bigcup _{s\in L}{\mathrm{Pref}}_L(s)=\{t|s=tu;s\in L;t,u\in \mathrm{Alph}(L{)}^{*}\}$

Exemplo:
$L=\left\{abc\right\}\text{ then }\mathrm{Pref}(L)=\{\epsilon ,a,ab,abc\}$

Uma linguagem é chamada fechada em prefixo se $\mathrm{Pref}(L)=L$.

O operador de conjectura de prefixo é idempotente:

$\mathrm{Pref}(\mathrm{Pref}(L))=\mathrm{Pref}(L)$

A relação de prefixo é a relação binária $⊑$ tal que $s⊑t$ se e somente se $s\in {\mathrm{Pref}}_L(t)$. Essa relação é um exemplo particular de uma ordem de prefixo.

Ver também

• Cadeia de caracteres

Referências

• Predefinição:Citar livro (See chapter 3.)