Definiciones-alfabetosycadenas

DEFINICIONES:

SÍMBOLO.- Es una representación tangible de algo abstracto, por ejemplo una letra es un símbolo gráfico que representa un sonido concreto, un dígito es la representación de un valor numérico, etc.
En particular, un símbolo puede ser un signo, un dígito, una letra o incluso un grupo de letras en algún lenguaje particular y que tiene algún significado convencional.

ALFABETO.-Es un conjunto, finito y no vacío de símbolos. En ocasiones se establece un orden convencional entre los símbolos, al cual se le llama orden alfabético, pero el orden no es una característica propia de los alfabetos, ya que esta propiedad no se requiere para la mayoría de las aplicaciones de lenguajes.

POR EJEMPLO:
➢ Σ = {0,1} es un alfabeto.
➢ El alfabeto griego: Σ = {α, β, γ, δ, ε, .. . , ω}
➢ El alfabeto para un programa de cómputo: Σ = {import, for, if, while, switch, and, . . . , or}

PROPIEDADES DE LOS ALFABETOS
Los alfabetos permiten las operaciones que son comunes a cualquier otra clase de conjuntos, siempre que el resultado de tal operación no sea un conjunto vacío. Esto es, si Σ1 y Σ2 son dos alfabetos, entonces los resultados de las siguientes operaciones:a) Σ1 U Σ2 es un alfabeto
b) Σ1 ∩ Σ2 es un alfabeto si Σ1 y Σ2 no son disjuntos
c) Σ1 - Σ2 es un alfabeto si Σ1[pic]Σ2
d) Σ2 – Σ1 es un alfabeto si Σ2[pic]Σ1
e) Σ1[pic] Σ2 es la diferencia simétrica de 2 alfabetos, y es un alfabeto si Σ1 ≠ Σ2.
f) Dado que no existe un alfabeto universal, porque tendría que ser infinito (y esto contradice la definición), tampoco puedeexistir el complemento de un alfabeto.

CADENA.- Es una secuencia finita de símbolos de un alfabeto dado, yuxtapuesto uno a continuación del otro en una secuencia determinada. La posición que ocupa cada símbolo dentro de la cadena lo diferencia de las demás ocurrencias del mismo, y por ello, cada símbolo puede apareceré numerosas veces dentro de una misma cadena.

CADENA VACÍA.- Se denota por ε yes la cadena está formada por una secuencia de cero símbolos de cualquier alfabeto.

OPERACIONES CON CADENAS

LONGITUD DE UNA CADENA
Si w es una cadena, se dice que la longitud de la misma es el número de símbolos que la forman y se denota por |w|. No importando cuantas veces aparezca el mismo símbolo en la cadena, cada ocurrencia se cuenta por separado.

CONCATENACIÓN.- Es layuxtaposición de dos cadenas, una a continuación de la otra, de tal forma que si w y x son dos cadenas, la concatenación de w con x es la cadena que se obtiene de añadir la cadena x a la cadena w.

Se denota con el operador de yuxtaposición: w•x.

➢ La yuxtaposición no es conmutativa: w•x ≠ x•w, aunque generalmente solamente se indica de la forma: wx
➢ La longitud de la concatenación es igual ala suma de las longitudes de las cadenas individuales: |w•x|= |w| + |x| = |x•w|
➢ La concatenación de ε con cualquier cadena w no modifica a w, es decir, la cadena vacía es el idéntico respecto a la concatenación, ya que: εw = wε = w
POTENCIA DE CADENAS.- Sea una cadena formada a partir de un alfabeto Σ, entonces para cualquier n ≥0, se tiene que la enésima potencia de w se puede definirrecursivamente como:

ε para n = 0
wn =
wwn-1 para n > 0

Se debe tener presente que (wx)n ≠ wnxn

PREFIJO.- Sea w una cadena formada a partir de un alfabeto Σ, entonces, se cumple que existen dos cadenas x y z, tales que w = xz, se cie que x es un prefijo de w. Además, cuando z ≠ ε ( es decir x ≠ w), se dice que x es un prefijo propio de w; en el otro caso, cuando x= w, se tiene que x es llamado prefijo impropio.
Una cadena de longitud n, tiene n prefijos propios distintos y uno impropio.

SUFIJO.- Sea w una cadena formada a partir de un alfabeto Σ, entonces, se cumple que existen dos cadenas x y z, tales que w = xz, se dice que z es un sufijo de w. Además, si x ≠ ε ( es decir z ≠ w), se puede decir que z es un sufijo propio de w; y similarmente al...