Calimero0000: Criou nova página com '{{Sem-fontes|data=fevereiro de 2011| angola=| arte=| Brasil=| ciência=| geografia=| música=| Portugal=| sociedade=|1=|2=|3=|4=|5=|6=}} Em programação e em [[lingu...'

2013-04-23T20:33:37Z

Criou nova página com '{{Sem-fontes|data=fevereiro de 2011| angola=| arte=| Brasil=| ciência=| geografia=| música=| Portugal=| sociedade=|1=|2=|3=|4=|5=|6=}} Em programação e em [[lingu...'

Página nova

{{Sem-fontes|data=fevereiro de 2011| angola=| arte=| Brasil=| ciência=| geografia=| música=| Portugal=| sociedade=|1=|2=|3=|4=|5=|6=}}
Em [[programação]] e em [[linguagens formais]], uma '''cadeia de caracteres''' (também conhecida como '''samblagem''' ou '''string''') é uma sequência ordenada de [[caractere]]s (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 (programação)|variável]] declarada com [[tipo de dado]] cadeia geralmente armazena um número pré-determinado de caracteres.

== Teoria formal ==
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'', <math>\Sigma^{*} = \bigcup_{n=0}^{\infty}\Sigma^{n}</math>. 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 ===
''[[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'' = <tt>bear</tt> e ''t'' = <tt>hug</tt>, então ''st'' = <tt>bearhug</tt> e ''ts'' = <tt>hugbear</tt>.

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 sub-cadeia (ou fator) de ''t'' se existem cadeias (possivelmente vazias) ''u'' e ''v'' de forma que ''t'' = ''usv''.

=== Ordenação lexicográfica ===
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 ==
Um [[tipo de dado]] ''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 [[linguagem de programação|linguagens de programação]]. Em algumas linguagens esse tipo é definido nativamente, em outras é um tipo composto, derivado.

{{esboço-programação}}

{{DEFAULTSORT:Cadeia Caracteres}}
[[Categoria:Estruturas de dados]]
[[Categoria:Tipos de dados]]
[[Categoria:Linguagens formais]]

Cadeia de caracteres - Histórico de revisões

Calimero0000: Criou nova página com '{{Sem-fontes|data=fevereiro de 2011| angola=| arte=| Brasil=| ciência=| geografia=| música=| Portugal=| sociedade=|1=|2=|3=|4=|5=|6=}} Em programação e em [[lingu...'