Una cadena ω (también palabra, frase o sentencia) es una sucesión finita de símbolos, sobre un alfabeto Σ.

Una cadena es

ω = s ₁ s ₂... s _n donde s ₁,s ₂,... s _n ∈ Σ
y el símbolo s _i 1 ≤ i ≤ n, ocurre en la posición i de la cadena.

Cadena Vacía

Por convención, ε denota la cadena vacía (la cadena que no tiene símbolos).

Ejemplos

Si Β = {0,1}, son cadenas sobre Β:

α₁ = 0101
α₂ = 1111
α₃ = 0111000
α₄ = ε

Operaciones sobre Cadenas

Sean dos cadenas sobre el alfabeto Α

ω=a ₁,a ₂,... a _n y η=b ₁,b ₂,... b _m a _i,b _j ∈ Α

Longitud de una cadena:

|ω| denota la longitud de la cadena ω

Igualdad

ω=η si |ω|=|η| y (∀i: i 1 ≤ i ≤ |ω|: a _i=b _i)

Reversa

ω^R denota la reversa de la cadena ω
ω^R = a _n, a _n-1,... a ₂, a ₁

Concatenación

ω⋅η denota la concatenación, la cual consiste en la en la secuencia de símbolos de ω seguidos de los de η
ω⋅η = a ₁,a ₂,... a _n, b ₁,b ₂,... b _m

Exponenciacion

ω^k denota la concatenación de ω con si misma k-1 veces
ω⁰ = ε, la Cadena vacía
ω^k=ω^k-1⋅ω

Ejemplos

A continuación se calculan algunas operaciones para las cadenas α₁, α₂, α₃, y α₄ del ejemplo dado en la definición de cadenas:

Longitud

• |α₁| = |0101| = 4
• |α₄| = |ε| = 0

Reversa:

• α₁^R = 1010

Concatenación

• α₁⋅α₂ = 01011111
• α₂⋅α₄ = 1111
• α₂⋅α₂ = 11111111

Potencia

• α₂³ = α₂⋅α₂⋅α₂ = 111111111111
• α₁⁴ = 0101010101010101

Clausura

Definimos Σ^*, la Clausura sobe Σ, como el conjunto de todas las posibles cadenas finitas sobre un Alfabeto Σ. Se conoce también como Clausura de Kleene, se denota como Σ^*, y se define así:

ε ∈ Σ^* ; la cadena vacía pertenece a la clausura
a ∈ Σ ⇒ a ∈ Σ^* _; todo elemento en Σ pertenece a la clausura
ω, η ∈ Σ ⇒ ω⋅η ∈ Σ^* ; la concatenación de cualquier par de elementos en la clausura también pertenece a la clausura

Formalmente, la clausura constituye un monoide sobre el conjunto Σ y la operación de concatenación.

Otras definiciones útiles

Definimos:

• Σ^k como todas las cadenas sobre Σ de longitud k:
  Σ^k = ω ∈ Σ^*, |ω| = k
• Σ⁺ como todas las cadenas sobre Σ de longitud mayor o igual a uno:
  Σ⁺ = Σ^* - {ε}