Teoria Computacional

Alfabetos.
Un vocabulario o alfabeto es un conjunto finito de símbolos, no vacío. Para definir que un símbolo a pertenece a un alfabeto V.
Los alfabetos se definen por enumeración de los símbolosque contienen, podemos ver los siguientes ejemplos:
·   V1={A,B,C,D,E,F,…..,X,Y,Z}
·   V2={a,b,c,d,0,1,2,3,4,*,#,+}
·   V3={0,1}
·   V4={if, then, begin, end, else, a,b,;,=,>}
·   También sepueden definir las tablas ASCII y EBCDIC como los alfabetos de distintos ordenadores.
Potencia de un alfabeto
Si  es un alfabeto, es posible expresar el conjunto de todas las cadenas de cierta longitudde dicho alfabeto utilizando una notación exponencial. Definimos como .
Como el conjunto de cadenas de longitud k, tales que todos los símbolos que las forman pertenecen a . 
CADENA
Una cadena esuna secuencia finita de símbolos de un determinado alfabeto.
Ejm. Tomando en cuenta los alfabetos o vocabularios definidos anteriormente, podemos decir que:
abcb es una cadena del alfabeto V2
a+2*bes una cadena del alfabeto V2
000111 es una cadena del alfabeto V3
If a>b then b=a; es una cadena del alfabeto V4
Prefijos y Sufijos
Los prefijos de una cadena están formados por los primerossímbolos de esta, y los sufijos, por los últimos. Un prefijo o sufijo de una cadena que no sea la misma cadena es un prefijo o sufijo propios. 


Subcadena
Una subcadena es una parte de la cadena a laque pertenece. Es decir, x es una subcadena de y si x es parte de y. Más formalmente, x es subcadena de y si y solo si existen z, w tales que zxw = y. Además, x es subcadena propia de y si y solo siexisten z, w siendo alguna de ellas no vacía, tales que zxw = y. (Es decir, se pide que x sea distinta de y para considerarla subcadena propia).
Cadena Vacía
Se denomina cadena vacía, que no tienesímbolos y se denota con l, por lo que su longitud es :
| l | ® 0
Longitud de Cadena
La longitud de una cadena consiste en el número de símbolos pertenecientes a la cadena. Ejm. Tomando en cuenta...