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 É 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)=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 Hopcroft, Ullman (1979), Sect.3.2, p.60

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.Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60 Similarmente, linguagens livres de contexto são fechadas sobre substituição de cadeia.Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131Contudo 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.

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 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.Formalmente, um homomofismo retorna uma linguagem que consiste em apenas uma cadeia, i.e. f(a) = {s}.Hopcroft, Ullman (1979), Sect.3.2, p.60-61

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.Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61 Similarmente, as gramáticas livre-de-contexto são fechadas sobre homomorfismosIsto segue da conjectura de substituição de cadeias sobre substituições arbitrarias. e homomorfismos invertidos.Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132

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 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 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 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 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 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 Cadeia de caracteres

Notas

Referências

(See chapter 3.)

Categoria:Linguagens formais