Conceptos teoría computacional

Símbolo: es una representación tangible de algo abstracto, por lo tanto, es perceptible por medio de al menos uno de los sentidos, por ejemplo, una letra es un símbolo gráfico que representa un sonido concreto; los símbolos también pueden representar un concepto o una idea, como los que se emplean en arquitectura, electricidad y matemáticas.
Alfabeto: es un conjunto, finito y no vacío desímbolos. Ejemplo X={0,1} es un alfabeto. El alfabeto de un programa de cómputo puede ser: X={end,for,get,if} en este caso, cada símbolo está formado por varias letras.
Propiedades de 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. Ejemplo sean los alfabetos Σ1={0,1,2,3,4} y Σ2={0,2,a,b},entonces tenemos que también son alfabetos los siguientes: Σ1UΣ2={0,1,2,3,4,a,b}
Cadena: es una secuencia finita de símbolos de un alfabeto dado, yuxtapuestos uno a continuación de 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 eso cada símbolo puede aparecer numerosas veces dentro de una misma cadena.Ejemplo: sea el alfabeto Σ={0,1}, entonces w1=10, w2=10011 y w3=100100101 son cadenas formadas a partir de ese alfabeto.
Cadena vacía: se denota por ε y es la cadena que está formada por una secuencia de cero símbolos de cualquier alfabeto.
Operaciones con cadenas: Longitud de una cadena: Si w es una cadena, decimos que la longitud de la misma es el número de símbolos que la forman y se denotapor |w|. No importando cuántas veces aparezca el mismo símbolo en la cadena, cada concurrencia se cuenta por separado. Ejemplo: Sea w1=10011, entonces |w1|=5.
Concatenación: es la yuxtaposició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. Ejemplo: Sean w=001 yx=1, entonces w•x=0011, mientras que x•w=1001.
Potencia de cadenas: Sea w una cadena formada a partir de un alfabeto Σ, entonces para cualquier n≥0 , se tiene que la enésima potencia de w se puede definir recursivamente como:

Ejemplo: sea w=0 entonces w0= ε, w1=0, w2=00, w3=000, w4=0000,etc.
Prefijo de una cadena: Sea w una cadena formada a partir de un alfabeto Σ, entonces, se cumple queexisten dos cadenas x y z, tales que w=xz, se dices que es x es un prefijo de w. Una cadena de longitud n, tiene n prefijos propios distintos y uno impropio. Ejemplo x0= ε, x1=c, x2=co, x3=cof, x4=cofr son prefijos de w=cofre.
Sufijo de una cadena: 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.Ejemplo: z0= ε,z1=a,z2=aa,z3=aaa y z4=aaaa son los sufijos propios de w=a5.
Subcadenas: Una cadena y es una subcadena de otra cadena w, si existen x y z, no ambas vacias, para las cuales se cumple que w=xyz. Cualquier prefijo o sufijo propios de w también son subcadenas de w, en particular, ε es una subcadena de cualquier otra cadena.
Cantidad máxima de subcadenas de una cadena: La cantidadmáxima N de subcadenas distintas de una cadena dada de longitud n, se puede determinar con la siguiente fórmula:


Inversa de una cadena: La inversa de una cadena w es la cadena wR, tal que es la imagen refleja de w, es decir, que equivale a w cuando se lee de derecha a izquierda.
Formalmente se define la inversa de w de manera recursiva como:

Donde y es una cadena y a es un símboloPropiedades de la inversa de una cadena:
• aR=a, donde a es un símbolo.
• (xR)R=x.
• Si x=wy, entonces xR=yRwR.
• Una cadena se llama palíndroma, cuando es igual a su inversa: w=wR.
Ejemplo: Obtener la inversa de la cadena w=amor.


Lenguaje formal: es un conjunto de palabras o cadenas formadas a partir de los símbolos de un alfabeto dado. Un lenguaje puede ser finito o infinito,...