Alfabetos, Cadenas y Lenguajes

1. Alfabeto

1.1. $\displaystyle \Sigma = \left\{ a,b,c,d,e,f,g,h,i,j,k,l,m,n,\textrm{\~n},o,p,q,r,s,t,u,v,w,x,y,z\right\}, $

1.2. Conjunto de símbolos finito y no vacío.Convencionalmente se utiliza el símbolo S para designar un alfabeto.

2. Cadenas

2.1. La cadena vacía, denotada por E es aquella que presenta cero apariciones de símbolos, es una cadena que puede construirse en cualquier alfabeto.

3. Lenguaje

3.1. Un lenguaje es un conjunto de cadenas, todas ellas seleccionadas de un S* donde S es un determinado alfabeto

4. Las principales ideas matemáticas necesarias para la compresión a la Teoría de Autómatas son conceptos que incluyen grafos, árboles, conjuntos, relaciones, cadenas, lenguajes abstractos e inducción matemática.

5. Un "símbolo" es una entidad abstracta. Las letras y los dígitos son ejemplos de símbolos usados con frecuencia. Una cadena (o palabra) es una secuencia finita de símbolos yuxtapuestos

5.1. Por ejemplo a, b y c son símbolos y casa es una cadena. La longitud de una cadena w que se denota como |w|, es el número de símbolos que componen la cadena. Por ejemplo casa tiene una longitud 4.

6. Otro lenguaje es el conjunto de cadenas sobre un alfabeto fijo S Denotamos a este lenguaje como S* Por ejemplo:

6.1. Si S = {a}, entonces S* = {E, a, aa, aaa,...}. Si S = {0,1}, entonces S* = {E,0,1,00,01,10,11,000,...}