Operações em cadeias de caracteres
Este artigo ou parte de seu texto pode não ser de natureza enciclopédica. (Fevereiro de 2015) |
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]![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3a/Magnifying_glass_01.svg/17px-Magnifying_glass_01.svg.png)
É 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 s ∈ L. 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
- L ⊆ f−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]- ↑ 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.
- ↑ Formalmente, um homomofismo retorna uma linguagem que consiste em apenas uma cadeia, i.e. f(a) = {s}.
- ↑ 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.)
- ↑ Hopcroft, Ullman (1979), Sect.3.2, p.60
- ↑ Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60
- ↑ Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131
- ↑ Hopcroft, Ullman (1979), Sect.3.2, p.60-61
- ↑ Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61
- ↑ Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132