This page last changed on Oct 08, 2006 by juanca.

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

Una cadena es

ω = s 1 s 2... s n donde s 1,s 2,... 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 Β:

α1 = 0101
α2 = 1111
α3 = 0111000
α4 = ε

Operaciones sobre Cadenas

Sean dos cadenas sobre el alfabeto Α

ω=a 1,a 2,... a n y η=b 1,b 2,... 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 2, a 1

Concatenación

ω⋅η denota la concatenación, la cual consiste en la en la secuencia de símbolos de ω seguidos de los de η
ω⋅η = a 1,a 2,... a n, b 1,b 2,... b m

Exponenciacion

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

Ejemplos

A continuación se calculan algunas operaciones para las cadenas α1, α2, α3, y α4 del ejemplo dado en la definición de cadenas:

Longitud
  • 1| = |0101| = 4
  • 4| = |ε| = 0
Reversa:
  • α1R = 1010
Concatenación
  • α1⋅α2 = 01011111
  • α2⋅α4 = 1111
  • α2⋅α2 = 11111111
Potencia
  • α23 = α2⋅α2⋅α2 = 111111111111
  • α14 = 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:
    Σ+ = Σ* - {ε}
Document generated by Confluence on Oct 04, 2010 11:25