Trabajo De Automatas
Enviado por respaldo • 15 de Febrero de 2014 • 567 Palabras (3 Páginas) • 198 Visitas
Cadenas, Alfabetos y Lenguajes
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.
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. 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.
Habitualmente, se emplean las letras minúsculas del principio del alfabeto (o dígitos) para designar a los símbolos y las letras minúsculas del final del alfabeto, normalmente w, x, y y z, para designar cadenas.
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.
La concatenación de dos
cadenas es la cadena que se forma al escribir la primera seguida de la segunda,
sin que haya espacio entre ellas, Por ejemplo la concatenación de padre y madre
es padremadre. La yuxtaposición se utiliza como el operador de concatenación.
Esto es si w y x son cadenas, entonces wx es la concatenación de estas dos
cadenas. La cadena vacía es la identidad para el operador de concatenación, es
decir Ew=wE para
cada cadena de w.
Un alfabeto es un conjunto de símbolos finito y no vacío.Convencionalmente se utiliza el símbolo S para designar un alfabeto.
Un
lenguaje es un conjunto de cadenas, todas ellas seleccionadas de un S* donde S es un determinado alfabeto
El conjunto vacío Ø y el conjunto formado por la cadena vacía { E } son lenguajes.
...