Lenguajes Autómatas

1. Alfabetos

1.1. Conjunto de símbolos A={a,b,c,d, ….z}

1.2. Un alfabeto es un conjunto no vacío y finito de símbolos.

1.3. alfabeto

2. Compilador

2.1. Es un traductor que convierte un texto escrito en un lenguaje fuente de alto nivel en un programa objeto en código máquina.

2.2. Fases de un Compilador

2.2.1. Análisis Léxico: Esta fase se encarga de verificar si todas las cadenas pertenecen o no al lenguaje.

2.2.2. Análisis Sintáctico: En esta fase se analiza la estructura de las expresiones en base a gramáticas.

2.2.3. Análisis Semántico: Este análisis es más dificil de formalizar, determina el tipo de los resultados intermedios, comprobar que los argumentos que tienen un operador pertenecen al conjunto de operadores posible, y si son compatibles entre sì.

2.3. Ventajas

2.3.1. El programa se compila una sola vez, pero se puede ejecutar muchas.

2.3.2. La ejecuci´on del programa objeto es mucho m´as r´apida que la interpretacion del fuente.

2.3.3. El compilador tiene una visi´on completa del programa, por lo que puede dar una informaci´on m´as detallada de los errores cometidos por el programador.

2.4. Características

2.4.1. Front End: parte que analiza el código fuente, comprueba su validez, genera el árbol de derivación y rellena los valores de la tabla de símbolos. Parte que suele ser independiente de la plataforma o sistema operativo para el que funcionará.

2.4.2. Back End: parte en donde se genera el código máquina exclusivo para una plataforma a partir de lo analizado en el front end. Por lo general el resultado del back end no puede ser ejecutado directamente, se necesita pasar por un proceso de enlazado (linker).

3. Operaciones con cadenas

3.1. La concatenación de dos cadenas w con z es la cadena que se obtiene al añadir a la cadena w la cadena z. Se denota por wz o w·z. La potencia de una palabra w sobre un alfabeto se define para n  N como:

3.1.1. union

3.1.2. concatenacion

3.1.3. cerradura de kleene

3.1.4. cerradura positiva

4. SUBCADENAS

4.1. Una cadena w es una u subpalabra de una cadena z si existen las cadenas x e y para las cuales z = xwy. La inversa o traspuesta de una palabra w es la imagen refleja de w.

5. Traductor

5.1. Es una máquina teórica que tiene como entrada un texto escrito en un lenguaje L1 y como salida un texto escrito en un lenguaje L2. Habitualmente se denomina a L1 lenguaje fuente y a L2 lenguaje objeto.

6. BIBLIOGRAFIA

6.1. TEORIA DE AUTOMATAS Y LENGUAJES FORMALES

6.2. AUTOMATAS Y LENGUAJES ( un enfoque dediseño),Ramon Brena, 2003.

6.3. AUTÓMATAS Y LENGUAJES FORMALES, Edgar Alberto Quiroga Rojas, 2008.

6.4. Teoría de autómatas) lenguajes formales, Dean Kelley, 1995.

6.5. AUTOMATAS, Michelle Brenes

7. Cadenas

7.1. Concatenación de símbolos pertenecientes a un alfabeto A={a,b,c,d, ….z}

7.2. Cadena Vacia

7.2.1. La cadena vacía es aquella cadena que presenta cero apariciones de símbolos. Esta cadena, designada por ε, es una cadena que puede construirse en cualquier alfabeto.

7.3. Longitud de una cadena

7.3.1. Suele ser útil clasificar las cadenas por su longitud, es decir, el número de posiciones ocupadas por símbolos dentro de la cadena. Por ejemplo, 01101 tiene una longitud de 5.

7.4. Concatenación de cadenas

7.4.1. Sean x e y dos cadenas. Entonces, xy denota la concatenación de x e y, es decir, la cadena formada por una copia de x seguida de una copia de

8. Lenguajes

8.1. Un conjunto de cadenas, todas ellas seleccionadas de un Σ∗, donde Σ es un determinado alfabeto se denominan lenguaje

8.2. TIPOS

8.2.1. alto nivel

8.2.1.1. son aquellos que se encuentran mas cercanos al lenguaje natural que al lenguaje maquina

8.2.2. medio nivel

8.2.2.1. son los lenguajes que se encuentran en un punto intermedio de los lenguajes antes mencionados

8.2.3. bajo nivel

8.2.3.1. lenguaje maquina

8.2.3.2. leguaje ensamblador

9. Es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”

9.1. El autómata: es un ordenador analógico. Se trata de dispositivo electrónico o hidráulico diseñado para manipular la entrada de datos

9.1.1. tipos de autómatas

9.1.1.1. Autómatas Finitos

9.1.1.2. Autómatas de Pila

9.1.1.3. Máquina de Turing

9.1.2. Aplicaciones

9.1.2.1. La disminución de tamaño y el menor costo han permitido que los autómatas sean utilizados en todos los sectores de la industria