ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Trabajo De Automatas


Enviado por   •  15 de Febrero de 2014  •  567 Palabras (3 Páginas)  •  210 Visitas

Página 1 de 3

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.

El conjunto de palíndromos (cadenas que

se leen igual de izquierda a derecha y viceversa) sobre el alfabeto {0,1} es un

lenguaje infinito. Algunos elementos de este lenguaje son E,0,1, 00, 01,010, y 1101011.

Por consiguiente vemos que el conjunto de todos

los palíndromos sobre una colección finita de símbolos no es, técnicamente

hablando, un lenguaje, porque sus cadenas no

se construyen colectivamente a partir de un alfabeto.

Otro lenguaje es el conjunto de cadenas

sobre un alfabeto fijo S Denotamos a este lenguaje

como S*

Por ejemplo:

...

Descargar como (para miembros actualizados) txt (3 Kb)
Leer 2 páginas más »
Disponible sólo en Clubensayos.com