Cadeia de caracteres

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Strings)
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes fiáveis e independentes. (desde fevereiro de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Em programação e em linguagens formais, uma cadeia de caracteres (também conhecida como samblagem ou string) é uma sequência ordenada de caracteres (símbolos) escolhidos a partir de um conjunto pré-determinado. Em programação, cada símbolo armazenado na memória é representado por um valor numérico. Uma variável declarada com tipo de dado cadeia geralmente armazena um número pré-determinado de caracteres.

Teoria formal[editar | editar código-fonte]

Seja Σ um alfabeto, um conjunto finito e não vazio. Os elementos de Σ são chamados caracteres. Uma cadeia sobre Σ é qualquer sequência finita de caracteres de Σ. Por exemplo, se Σ = {0, 1}, então 0101 é uma cadeia sobre Σ. O tamanho da cadeia é a quantidade de caracteres, e pode ser qualquer valor inteiro não negativo. A cadeia vazia é uma cadeia única sobre Σ de tamanho 0, sendo denotada por ε ou λ.

O conjunto de todas as cadeias sobre Σ de tamanho n é denotado por Σn. Por exemplo, se Σ = {0, 1}, então Σ² = {00, 01, 10, 11}. Note que Σ0 = {ε} para qualquer alfabeto Σ. O conjunto de todas as cadeias sobre Σ de qualquer tamanho é denotado por Σ*. Em termos de Σn, \Sigma^{*} = \bigcup_{n=0}^{\infty}\Sigma^{n}. Por exemplo, se Σ = {0, 1}, Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}. Apesar do conjunto Σ* ser infinito, todos os elementos de Σ* possuem tamanho finito.

Um conjunto de cadeias sobre Σ (isto é, qualquer sub-conjunto de Σ*) é chamado uma linguagem formal sobre Σ.

Concatenação e sub-cadeias[editar | editar código-fonte]

Concatenação é uma importante operação binária em Σ*. Para qualquer duas cadeias s e t em Σ*, sua concatenação é definida pela sequência de caracteres de s seguida pela sequência de caracteres em t, denotada por st. Por exemplo se Σ = {a, b, …, z}, s = bear e t = hug, então st = bearhug e ts = hugbear.

A concatenação de cadeias é uma operação associativa, mas não comutativa. A cadeia vazia serve como um elemento identidade; par qualquer cadeia s, εs = sε = s. Portanto, o conjunto Σ* e a operação de concatenação formam um monóide.

A cadeia s é dita uma subcadeia (ou fator) de t se existem cadeias (possivelmente vazias) u e v de forma que t = usv.

Ordenação lexicográfica[editar | editar código-fonte]

Geralmente é necessário definir uma ordenação em um conjunto de cadeias. Se um alfabeto Σ possui uma relação de ordem (como a ordem alfabética) pode-se definir uma relação de ordem em Σ* chamada ordem lexicográfica. Note que como Σ é finito, é sempre possível definir uma ordenação em Σ e portanto em Σ*. Por exemplo, se Σ = {0, 1} e 0 < 1, então a ordenação lexicográfica em Σ* é ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 …

Cadeia de caracteres como tipo de dado[editar | editar código-fonte]

Um tipo de dado quanticos cadeia de caracteres (referido em programação geralmente como string) é uma modelagem de uma cadeia formal de caracteres. São bastante usados em programação, sendo implementados em quase todas as linguagens de programação. Em algumas linguagens esse tipo é definido nativamente, em outras é um tipo composto, derivado.

Ícone de esboço Este artigo sobre programação de computadores é um esboço. Você pode ajudar a Wikipédia expandindo-o.