Operações em cadeias de caracteres

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Emblem-question.svg
Este artigo ou se(c)ção pode conter texto de natureza não enciclopédica. (desde fevereiro de 2015)
Justifique o uso dessa marcação e tente resolver essas questões na página de discussão.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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)=La onde La ⊆ Δ* é 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 sL. Substituições de cadeias podem ser estendidas a linguagens inteias como [1]

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.[2] Similarmente, linguagens livres de contexto são fechadas sobre substituição de cadeia.[3][note 1]

Um simples exemplo é uma conversão fuc(.) à 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 fuc para cadeias, temos e.g.

  • fuc(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
  • fuc(‹u2›) = {‹U} ⋅ {ε} = {‹U›}, and
  • fuc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Para a extensão de fuc para linguagens, temos e.g.

  • fuc({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.

Para a extensão de fuc para cadeias, temos e.g.

  • fuc(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
  • fuc(‹u2›) = {‹U} ⋅ {ε} = {‹U›}, e
  • fuc(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.

Para a extensão de fuc para linguagens, temos e.g.

  • fuc({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.

Um outro exemplo é a conversão de uma cadeia ASC codificada.

Homomorfismo de cadeia[editar | editar código-fonte]

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.[note 2][4]

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

Lf−1(f(L))

para cada linguagem L.

A classe de linguagens regulares é fechada sobre homomorfismos e homomorfismos invertidos.[5] Similarmente, as gramáticas livre-de-contexto são fechadas sobre homomorfismos[note 3] e homomorfismos invertidos.[6]

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

Exemplos de imagens homomorficas invertidas são

  • guc−1({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since guc(‹sss›) = guc(‹sß›) = guc(‹ßs›) = ‹SSS›, and
  • guc−1({ ‹A›, ‹bb› }) = { ‹a› }, since guc(‹a›) = ‹A›, enquanto ‹bb› não pode ser alcançado por guc.

Para a ultima language, guc(guc−1({ ‹A›, ‹bb› })) = guc({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. O homomorfismo guc não é ε-livre, uma vez que mapeia e.g. ‹0› para ε.

Projeção de cadeia[editar | editar código-fonte]

Se s é uma cadeia, e é um alfabeto, a projeção de cadeia de s é a cadeia que resulta em remover todas as letras que não estão em . É escrito como . É formalmente definido da remoção de letras do lado da mão direita.

Aqui 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

Quociente à direita[editar | editar código-fonte]

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

O quociente de uma cadeia vazia é pode ser obtido:

De modo similar, dado um subconjunto de um monoide , pode-se definir o subconjunto quociente como

Quocientes à esquerda podem ser definidos de maneira similar, com operações se colocando à esquerda de uma cadeia.

Relação sintática[editar | editar código-fonte]

O quociente à direita de um subconjunto de um monoide define uma relação de equivalencia, chamada de relação sintática à direita de S. É dada por

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

é 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[editar | editar código-fonte]

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

A cadeia vazia é sempre cancelável:

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

Prefixos[editar | editar código-fonte]

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

here . aqui .

A conjectura de prefixo de uma linguagem é

Exemplo:

Uma linguagem é chamada fechada em prefixo se .

O operador de conjectura de prefixo é idempotente:

A relação de prefixo é a relação binária tal que se e somente se . Essa relação é um exemplo particular de uma ordem de prefixo.

Ver também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. 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.
  2. Formalmente, um homomofismo retorna uma linguagem que consiste em apenas uma cadeia, i.e. f(a) = {s}.
  3. Isto segue da conjectura de substituição de cadeias sobre substituições arbitrarias.

Referências[editar | editar código-fonte]

  • 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.)
  1. Hopcroft, Ullman (1979), Sect.3.2, p.60
  2. Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60
  3. Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131
  4. Hopcroft, Ullman (1979), Sect.3.2, p.60-61
  5. Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61
  6. Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132