Teoría de Autómatas
De Computacion
La computación, muy avanzada hoy en día, sienta sus bases sobre una sólida plataforma desarrollada con mucho esfuerzo e investigación, un área importante es el trabajo con los lenguajes de programación, cuyas raíces están en la teoría de autómatas y lenguajes formales. Esta asignatura forma parte del área fundamental de la carrera de Ingeniería en Informática correspondiente al sexto semestre. Esta asignatura tiene su importancia en que señala los aspectos básicos de los lenguajes computacionales, así como nos muestra de manera general el trabajo interno de los sistemas de computación en lo referente al tratamiento de cadenas y lenguajes, los contenido que se cubren son principalmente los autómatas finitos, autómatas de pila, lenguajes independientes de contexto, maquinas de turing como reconocedores de lenguajes. Sea bienvenido al presente curso y no dude en contactar a su profesor en caso de necesitar resolver cualquier inquietud. Saludos y éxitos!!!
Tabla de contenidos
|
[editar] Objetivo General
Dar al estudiante una visión global del trabajo de los autómatas y su aplicación en los lenguajes de programación.
[editar] Objetivos Especificos
- Conocer como funcionan los lenguajes.
- Especificar lenguajes regulares y autómatas finitos para reconocimiento.
- Escribir programas de reconocimiento léxico.
- Especificar lenguajes independientes de contexto y autómatas de pila para reconocimiento.
- Construir máquinas de turíng para reconocer lenguajes.
- Escribir gramáticas de contexto libre.
- Escribir programas de análisis sintáctico
[editar] Bibliografia
Texto Base
Hopcroft, J., et All, Introducción a la Teoría de Autómatas, Lenguajes y Computación, Segunda Edición, Adison Wesley, Madrid, 2002
Este libro tiene un espectro amplio en cuanto a que cubre desde los detalles hasta aspectos avanzados de cada tema, está expresado en términos sencillos y solo en casos necesarios recurre a expresar con formalismos los diferentes aspectos que trata.
Texto Complementario
Kelley, D. Teoria de Autómatas y Lenguajes Formales, Prentice Hall, Madrid 1995 Escogido por los temas que cubre y principalmente por la amplia gama de ejercicios que resuelve y plantea, ofrece un capitulo especial (el número cero) dedicado a aquellos que tienen problemas con las matemáticas necesarias para abordar la materia. Su metodología la basa en definiciones cortas, ejercicios resueltos con explicaciones detalladas y muchos ejercicios planteados.
[editar] Desarrollo del Aprendiza
[editar] Capitulo 1: Automatas Finitos
[editar] Datos Generales
| Texto Base | Introduccion a la teoria de automatas, lenguaje y computacion | ||
| Capitulo | 1. Para que sirven los automatas? | ||
| Paginas | 1 - 6 | Horas de estudio empleadas para el desarrollo del contenido | 1 horas |
| Capitulo | 1.5 Conceptos centrales de la teoria de automatas | ||
| Paginas | 32 - 37 | Horas de estudio empleadas para el desarrollo del contenido | 1 Horas |
| Capitulo | 2 Automatas finitos | ||
| Paginas | 41 - 90 | Horas de estudio empleadas para el desarrollo del contenido | 10 Horas |
[editar] DESARROLLO
Estimado(a) estudiante, en este primer capitulo se van a tratar los temas iniciales de la Teoría de Autómatas, para un mejor entendimiento los temas se plantean en la siguiente tabla con recomendaciones que pueden guiar su trabajo.
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas |
|---|---|---|
| ¿Para qué sirven los autómatas finitos? | Descripción del uso de los autómatas | * Lectura de las páginas 1 y 2
|
| ¿Porqué estudiar teoría de autómatas? | Descripción de las aplicaciones de los autómatas, | * Lectura de las páginas 2, 3 y 4
|
| Representaciones estructurales | Descripción de la notación gramatical y expresiones regulares | * Lectura de la sección 1.1.2 del texto base |
| Autómatas y complejidad | * Lectura de la sección 1.1.3
| |
| Alfabetos, cadenas y lenguajes | Alfabetos, construcción de cadenas, operaciones con lenguajes | * Lectura de la sección 1..5 |
| Autómatas finitos: introducción | Generalidades sobre los autómatas finitos | * Lectura de las páginas 41 y 42
|
| Descripción informal de los autómatas finitos | Presentación del funcionamiento de un AF a través de un ejemplo | * Lectura de las páginas 42 – 50
|
| Autómatas finitos deterministas | Definición y graficación de autómatas | * Lectura de las páginas 50 – 60
|
| Autómatas finitos no deterministas | * Lectura de las páginas 61-74
|
[editar] Construcción de autómatas
Diseñar un AFD que acepte identificadores que inicien siempre con un guión bajo y luego puedan contener letras o dígitos.
Inicialmente debemos asociar la condición inicial al estado inicial, esto significa que desde el primer estado al segundo estado únicamente puede existir una transición que etiquetada con guión bajo
Una vez en el estado dos, se puede avanzar hacia el estado tres con una transición etiquetada con letra (L) o con digito (D).
Ahora es necesario que la cadena pueda tener mas letras o más dígitos, esto se puede conseguir haciendo que desde el estado 3 salga una arista etiquetada con letra (L) hacia otro estado (que puede ser el mismo estado 3). Lo mismo hay que hacer para reconocer más dígitos.
Desarrollemos ahora otro autómata que reconozca cadenas de letras (sobre el alfabeto {a,b}) en las que nunca puedan ir dos a’s seguidas
La condición inicial no esta asociada al estado inicial, el autómata puede empezar con una letra a o con una letra b
Ahora puede tener otra letra b con la que regresa al estado 1. Note que siempre termina en el estado 2.
Es posible construir autómatas que tengan transiciones vacías, es decir que sus aristas no tienen como etiqueta símbolos del alfabeto del autómata, en su lugar tienen vacío (ε), generalmente las transiciones vacías se utilizan para unir autómatas, como en el caso de la figura 2.19 de la página 81 del texto base.
[editar] Transformación de un AFN en un AFD.
El procedimiento consiste en agrupar los conjuntos de estados que tengan entradas y salidas (aristas) comunes, para ello se crea una tabla de transiciones (representación del AFD), esta matriz (llamada Matriz_de_D) tiene como índices el conjunto de estados (con aristas comunes) y los elementos del alfabeto.
Son necesarias tres operaciones cuyos resultados se requieren al aplicar el algoritmo de transformación:
Cerradura-ε de s.- Equivale al conjunto de estados del AFN que se pueden alcanzar des-de s sin consumir símbolos de la entrada (o lo que es lo mismo con transiciones-e). Esta operación devuelve un conjunto de elementos (estados).
Cerradura-e de T.- Sea T un conjunto de estados, esta operación equivale al conjunto de estados del AFN que se pueden alcanzar desde cada s en T sin consumir símbolos de la entrada (o lo que es lo mismo con transiciones-e). Esta operación devuelve un conjunto de elementos (estados).
Mueve (T, a).- Equivale al conjunto de estados que se pueden alcanzar con un símbolo a (arista etiquetada con a ) desde algún estado s de T. Esta operación devuelve un conjunto de elementos (estados).
En caso de tener problemas, recuerde que s es un estado; T es un conjunto de estados en donde cada uno en su momento se representa por s; a es un símbolo que etiqueta una arista que va desde un estado a otro.
Por conveniencia se denominan el AFN como N y el AFD como D.
Algoritmo 1. Inicio 2. A = Cerradura-ε de s0 /* Cerradura vacía del estado inicial del AFN */ 3. Agregar A al conjunto Estados_de_D /* Se crea un conjunto con el elemento A */ 4. Para cada conjunto del conjunto Estados_de_D /* Se recorre ese conjunto */ 5. T = Conjunto del conjunto Estados_de_D /* Se toma un elemento */ 6. Para cada elemento del alfabeto 7. a := elemento del alfabeto 8. U = Cerradura-e (mueve(T, a)) 9. Si U no está en Estados_de_D 10. Agregar U a Estados_de_D 11. FinSi 12. Matriz_de_D[T, a] := U 13. FinPara 14. FinPara 15. Fin_del_algoritmo
Como ejercicio vamos a tomar el diagrama del autómata no determinista siguiente:
Insertar Grafica
| A=Cerradura vacia de S0
A={0} | Del estado 0 solo se puede llegar a 0
sin consumir símbolos de entrada | |||||||||||||||||||
| Estados_de_D={A} | ||||||||||||||||||||
| T=A={0}
a = ‘a’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(0,’a’)) U=Cerrad-vacia(1) U={1,2,3,5,8}=B | T=A={0}
a = ‘b’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(0,’b’)) U=Cerrad-vacia(vacio) U=vacio; no se lo considera |
Se llena la matriz con las entradas (A,a)=B | ||||||||||||||||||
| Estados_de_D={A, B} | ||||||||||||||||||||
| T=B={1,2,3,5,8}
a = ‘a’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(1,2,3,5,8, ’a’)) U=Cerrad-vacia(4,9) U={2,3,4,5,7,8,9}=C | T=B={1,2,3,5,8}
a = ‘b’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(1,2,3,5,8, ’b’)) U=Cerrad-vacia(6) U={2,3,5,6,7,8}=D |
Se llena la matriz con las entradas (B,a)=C y (B,b)=D | ||||||||||||||||||
| Estados_de_D={A, B, C, D} | ||||||||||||||||||||
| T=C={2,3,4,5,7,8,9}
a = ‘a’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(2,3,4,5,7,8,9, ’a’)) U=Cerrad-vacia(4,9) U={2,3,4,5,7,8,9}=C (se repite) | T=C={2,3,4,5,7,8,9}
a = ‘b’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(2,3,4,5,7,8,9, ’b’)) U=Cerrad-vacia(6,10) U={2,3,5,6,7,8,10}=E |
Se llena la matriz con las entradas (C,a)=C y (C,b)=E | ||||||||||||||||||
| Estados_de_D={A, B, C, D, E} | ||||||||||||||||||||
| T=D={2,3,5,6,7,8}
a = ‘a’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(2,3,5,6,7,8, ’a’)) U=Cerrad-vacia(4,9) U={2,3,4,5,7,8,9}=C (se repite) |
T=D={2,3,5,6,7,8} a = ‘b’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(2,3,5,6,7,8 ’b’)) U=Cerrad-vacia(6) U={2,3,5,6,7,8}=D (se repite) |
Se llena la matriz con las entradas (D,a)=C y (D,b)=D | ||||||||||||||||||
| Estados_de_D={A, B, C, D, E} | ||||||||||||||||||||
| T=E={2,3,5,6,7,8,10}
a = ‘a’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(2,3,5,6,7,8,10, ’a’)) U=Cerrad-vacia(4,9) U={2,3,4,5,7,8,9}=C (se repite) |
T=E={2,3,5,6,7,8,10} a = ‘b’ U=Cerrad-vacia(Mueve(T,a)) U=Cerrad-vacia(Mueve(2,3,5,6,7,8,10, ’b’)) U=Cerrad-vacia(6) U={2,3,5,6,7,8}=D (se repite) |
Se llena la matriz con las entradas (E,a)=C y (E,b)=D |
Al graficar la matriz, el autómata resultante es el siguiente:
insertar grafica
[editar] Capitulo 2 Expresiones y Lenguajes Regulares
[editar] Datos Generales
| Texto Base | Introduccion a la teoria de automatas, lenguaje y computacion | ||
| Capitulo | 3. Expresiones y Lenguajes Regulares | ||
| Paginas | 1 - 6 | Horas de estudio empleadas para el
desarrollo del contenido | 12 horas |
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas |
|---|---|---|
| Expresiones regulares y lenguajes regulares | E-R, y operadores utilizados en la construcción de E-R | * Lectura de las páginas 91-94
|
| Construcción de E-R | Se detallan los pasos para construir E-R | * Lectura de las páginas 94-96
|
| Precedencia de operadores de E-R | Definición del orden de evaluación de las expresiones | * Lectura de las páginas 97-98
|
| Conversión de E-R en autómatas finitos | * Lectura de las páginas 111-117
|
[editar] Conversión de una expresión regular en autómata finito
Como conclusión de lo hasta ahora visto, es posible expresar mediante una expresión regular un lenguaje regular, por lo que ahora nos vamos a centrar en un proceso de transformación de una expresión regular a un autómata finito no determinista. El algoritmo que se presenta más adelante, se basa en el orden que tiene la construcción de la expresión regular y toma cada uno de sus componentes por separado, construyendo un AFN para cada componente; estos AFN se unifican en el mismo orden en que se expresa la expresión regular, dando como resultado un AFN que reconoce el lenguaje que genera la expresión regular en cuestión.
[editar] Algoritmo de transformación de una expresión regular en un AFN
Para cada uno de los componentes sintácticos de la E-R ejecutar los pasos uno y dos
Paso uno) Para ε (vacío) construya el autómata correspondiente.
Paso dos) Para cada símbolo a independiente de la expresión regular construya su autómata correspondiente.
En los dos casos i es el estado inicial y f el estado final o de aceptación de la subexpresión.
Combinar los autómatas resultantes de acuerdo a las guías del paso tres.
Paso tres) Si Se tiene dos AFN para las expresiones s y t
a) Para la expresión s . t construya el autómata finito siguiente:
Insertar Imagen
d) Para la expresión regular (s) (entre paréntesis) utilice el AFN que diagramó para s
Ejemplo: Para la expresión regular a (a + b)* ab obtener el AFN
Paso uno y paso dos)
Las expresiones que forman parte de la expresión regular son:
1. a
2. a
3. b
4. a
5. b
Note que para cada componente se requiere un AFN independiente.
Autómata para el componente 1
Autómata para el componente 2
Autómata para el componente 3
Autómata para el componente 4
Autómata para el componente 5
Paso 3)
Combinación de los autómatas a + b
Obtención de (a U b)*
Concatenación de a con (a U b)*
Concatenación de a (a U b)* con a
[editar] Capitulo 3 Analisis Lexico
[editar] Datos Generales
| Texto Base | No es necesario el texto base | ||
| Paginas | Horas de estudio empleadas para el desarrollo del contenido | 10 horas |
Para el desarrollo de este capitulo, no hace falta trabajar con el texto guía, trabajaremos únicamente con la guía didáctica, pero es necesario que primero lea el anexo A. Inicialmente veremos que es el análisis léxico, para lo cual es necesario comprender cual es el trabajo de un compilador y cuales son sus partes: Un compilador es un programa que convierte un programa escrito en un lenguaje de alto nivel en un programa en código objeto y luego en ejecutable. Ejemplo: Cuando usted escribe un programa en lenguaje C++, antes de hacerlo funcionar(correr) debe convertirlo en ejecutable, para ello utiliza un compilador. El compilador se encarga de verificar que no tenga errores y luego lo convierte en ejecutable (con extensión .EXE)
El compilador cumple los siguientes tres pasos:
1. Verificación de errores del programa fuente(código de alto nivel)
- Verificación de errores léxicos q Verificación de errores sintácticos q Verificación de errores semánticos
- Transformación del código de alto nivel en código objeto
- Transformación del código objeto en código maquina(ejecutable)
Lo anterior significa que el compilador esta formado por los siguientes módulos:
- Modulo léxico.- Encargado de verificar que no existan errores léxicos
- Modulo sintáctico.- Encargado de verificar que no existan errores sintácticos
- Modulo semántico.- Encargado de verificar que no existan errores semánticas
- Modulo generador de código objeto.- Encargado de convertir el programa fuente en programa objeto(código ensamblador)
- Encadenador.- Encargado de convertir el programa objeto en código o maquina programa ejecutable(unos y ceros)
Esquema de módulos de un compilador
Como conclusión podemos anotar que el analizador léxico (o modulo léxico) se encarga de verificar que todas las palabras escritas en el programa fuente pertenezcan al lenguaje de alto nivel en el que se escribe el programa. Ejemplo: Dado el programa
int main() {
int b=10;
cout << a+b;
retur 0;
}
El analizador léxico debe detectar que a+b es un error léxico porque a no ha sido declarada como variable.
De igual forma en la línea “retur 0”, el analizador léxico detectará que retur no es una palabra reservada (le falta una n al final)
Ya sabemos cual es la tarea de un analizador léxico, ahora veamos cuales son sus etapas.
Una vez escrito un programa fuente, para compilarlo(transformarlo), es necesario abrirlo y empezar a leerlo, luego se deben ir concatenando (uniendo) cada uno de sus caracteres para formar cadenas y a su vez hay que comprobar que cada cadena pertenezca al lenguaje en cuestión. Suponga que el lenguaje en cuestión es C++. Entonces hay que verificar que cada una de las cadenas del programa fuente sea una palabra reservada o un identificador. Observemos el programa:
1. int main() {
2. int b=10;
3. cout << a+b;
4. return 0;
5. }
En la línea 1 del archivo (quiero decir del programa) se van uniendo los caracteres i, n y finalmente la t para formar la cadena int (sabemos que la cadena termina en t por el espacio que le sigue “separador”) y luego hay verificar si esta cadena es una palabra reservada de C++ o es un identificador, caso contrario tendremos un error de tipo léxico. De igual manera procedemos con la cadena main, en lo que respecta a los paréntesis, el analizador debe ser lo suficientemente inteligente como para entender que son símbolos independientes de la cadena main y cuando los reconozca, debe retornar un indicador adecuado que permita saber que se reconoció un paréntesis.
Para comparar, es necesario que las palabras reservadas estén guardadas en alguna estructura, conceptualmente se maneja el termino tabla de símbolos, en ella se guardan las palabras reservadas y los identificadores(variables) que se declaran, cuando el analizador léxico forma una cadena, esta se compara con los elementos almacenados en esta tabla de símbolos. Primero se busca si es palabra reservada, si no es, se busca si es alguna variable ya declarada.
Resumiendo, podemos decir que las etapas del análisis léxico son:
- Apertura del archivo.
- Lectura de sus caracteres.
- Concatenación de caracteres.
- Comparación de las cadenas que se forman con los elementos de la tabla de símbolos.
- Retorno de un indicador de la cadena reconocida, también llamado token.
Especificación de componentes léxicos
Cuando se diseña un lenguaje de programación, es necesario definir cuales serán las palabras reservadas, que forma tendrán los identificadores, que formato tendrán los valores numéricos, etc. Esto depende del tipo de aplicación que se le vaya a dar al lenguaje de programación, por ejemplo si se quiere construir un lenguaje C++, será necesario incluir palabras como int, main, return, etc. Se debe definir que los identificadores inicien con una letra o con un número o con guion bajo y luego puedan contener letras o números, así mismo los valores numéricos deben iniciar con un número, luego debe n tener un punto decimal y luego pueden tener más números.
Las palabras reservadas serán fijas, pero los identificadores y valores numéricos pueden ser especificados con una expresión regular. Observe el siguiente ejemplo:
l d ¦ _ (l ¦ d ) (l ¦ d ¦ _)
Con esta expresión regular estamos indicando que los identificadores pueden iniciar con una letra o con un digito o con un guion bajo, luego deben tener una letra o un digito y después pueden tener letras, dígitos o guiones bajos.
En el caso de los valores numéricos, se puede especificar su formato con la siguiente expresión regular:
(d+.d+) ¦ (d+)
Estamos indicando que pueden empezar con uno o mas números, seguidos de un punto decimal y luego tener mas dígitos, o también pueden ser solamente números(sin punto decimal).
Recuerde que el símbolo ¦ (línea) significa o (para escoger una u otra opción).
En el siguiente cuadro se indica la diferencia entre lexema y componente léxico y token: En el siguiente cuadro se indica la diferencia entre lexema y componente léxico y token:
| Lexema | Componente Lexico | Token |
| Velocidad | ID | ID |
| 10 | NUM | NUM |
| Int | int | Int |
Observe que el lexema es la cadena que se encuentra en el archivo fuente, el componente léxico es una clasificación a la que pertenece el lexema y finalmente el token es el valor que retorna el analizador léxico una vez que reconoció un lexema. El token también puede ser un código que el diseñador le asigne a cada componente léxico. Concluyendo, los componentes léxicos se especifican a través de expresiones regulares, las mismas que luego deben ser programadas en el analizador léxico.
Reconocimiento de componentes léxicos
Con el fin de facilitar el entendimiento, vamos a dividir el reconocimiento de componentes léxicos en categorías (esto no es normal, sin embargo es útil), las categorías en las que podemos trabajar son:
- Palabras reservadas
- identificadores
- Valores numéricos
En todos los casos vamos a utilizar una tabla de símbolos (TDS), esta es una estructura que permite guardar información acerca de los componentes léxicos. Normalmente es una lista ligada con algunos atributos, observe la siguiente figura:
Lista ligada que representa una tabla de simbolos
La TDS es una estructura donde normalmente están guardadas todas las palabras reservadas del lenguaje de programación que se construye. El campo com_lex es el espacio en donde se guardan todas las palabras reservadas o los identificadores que forman parte del programa, el campo valor sirve para guardar los valores que puedan ir tomando las variables y el campo tipo sirve para indicar el tipo de dato que le corresponde a cada variable. En términos generales lo que el analizador léxico hace es formar una cadena con los caracteres del programa fuente y compararla con cada una de los nodos de la estructura. Normalmente la búsqueda (para la comparación), se da a través de algún tipo de hash o utilizando en lugar de una lista ligada un árbol B, con lo que se acelera la búsqueda. Para reconocer las palabras reservadas, el diseñador del lenguaje de programación puede optar por una expresión regular como la siguiente:
letra+
Que significa que una palabra reservada puede estar formada por una o mas letras.
Esta expresión regular transformada en seudocódigo puede quedar como sigue:
Abrir archivo fuente Mientras no sea fin de archivo /*****Con las siguientes 4 líneas vamos a formar la cadena ósea la palabra reservada
Vaciar la variable c /* inicializarla con vació
Leer el siguiente carácter
Si el carácter es una letra
Mientras el carácter es diferente de espacio
Agregar el carácter a c /* c es una variable */
Leer el siguiente carácter
Fin mientras
Fin si
/*****Ahora lo vamos a buscar en la TDS
Si el valor de c se halla en la TDS
Retornar c /* que es el token de la palabra reservada
Si no
Retornar ID /* que es el token para un identificador
Fin si
Fin mientras
Cerrar archivo
Como recordaran, el modulo léxico reconoce cadenas y retorna el token (símbolo) que las identifica, en el seudocódigo anterior se retorna ID en el caso de las palabras reservadas y se retorna la cadena misma, es decir la palabra reservada, en este caso es igual al token.
Para reconocer identificadores, podemos utilizar la siguiente expresión regular:
Ld _ (Ld)(Ld_)
Note que el símbolo significa o
Se puede empezar con letras, dígitos o guión bajo, como segundo carácter del identificador puede ir una letra o un digito y de ahí en adelante puede ir una letra, un digito o un guión bajo. Esa expresión regular puede representarse en pseudocódigo como se muestra a continuación.
Abrir archivo fuente
Mientras no sea fin de archivo /*****Con las siguientes 4 líneas vamos a formar la cadena ósea la palabra reservada
Vaciar la variable c /* inicializarla con vació
Leer el siguiente carácter
Si el carácter es una letra o un digito o un guion bajo
Mientras el carácter es letra o es digito o es guion bajo
Agregar el carácter a c /* c es una variable */
Leer el siguiente carácter
Fin mientras
Fin si /*****Ahora lo vamos a buscar en la TDS
Si el valor de c se halla en la TDS
Retornar c /* que es el token de la palabra reservada
Si no
Retornar ID /* que es el token para un identificador
Fin si
Fin mientras
Cerrar archivo
Con el código escrito podemos notar que no existe una forma de asegurarnos que el segundo carácter no sea un guión bajo, por lo que en ocasiones el código es algo mas difícil de implementar. Ante esto surge la necesidad de programar un autómata como veremos a continuación.
Autómata para reconocer identificadores en C++
Observe que el reconocimiento inicia en el estado cero y desde ahí se puede leer una letra o un digito (un número) o un guión bajo, se llega al estado uno y desde ahí leyendo letra o digito se traslada al estado dos, en donde se pueden leer letras dígitos o guiones, en cualquier caso serán identificadores válidos. Este autómata se puede programar, observe el siguiente procedimiento:
Inicio
Abrir archivo
Variable estado igual cero (estado=0)
Variable c igual vacío (c=””)
Mientras no sea fin de archivo y c sea diferente de espacio
Leer el siguiente carácter en c
En caso de que estado
Sea cero y c sea letra o digito o guión
Estado es igual a uno
Sea uno y c sea letra o digito
Estado es igual a dos
Sea dos y c sea letra o digito o guión
Estado es igual a dos
En cualquier otro caso Error léxico y terminar
Fin de caso
Fin mientras
Retornar ID
Cerrar archivo
Fin
Es posible programar autómatas para cualquier expresión regular, sin embargo cuando se trata de lenguajes de programación complejos, podemos hallarnos con dificultades en el reconocimiento de los componentes léxicos. A continuación se presenta un algoritmo tomado del texto Compiladores técnicas y herramientas del Dr. Alfred Aho, el mismo que resume de manera sencilla los diferentes aspectos que se deben tomar en cuenta al implementar un analizador léxico.
function analex: integer;
var buflex array[0..100] of char /* arreglo de longitud 100
c char;
begin
loop begin
lee un carácter en c
if c es un espacio en blanco o un símbolo tab then
no hacer nada;
else if c es un carácter de línea nueva then
numlinea :=numlinea + 1;
else if c es un digito then begin
asignar a valcomplex el valor de este y los dígitos siguientes;
return NUM;
end
else if c es una letra then begin
poner c y las letras y dígitos sucesivos en buflex;
buscar buflex en la TDS
if buflex no esta en la TDS then begin
insertar buflex en la TDS
return ID
end
end
else begin
asignar NINGUNO a valcomplex;
return el numero entero del carácter c;
end
end
end
La tarea es hacer funcionar de forma manual este algoritmo utilizando un archivo que contenga cadenas de caracteres.
[editar] Capitulo 4 Automatas a Pila
[editar] Datos Generales
| Texto Base | Introducción a la teoría de autómatas, lenguajes y computación | ||
| Capitulo del libro | 6. Automatas de Pila | ||
| Paginas | 235 - 272 | Horas de estudio empleadas para el desarrollo del contenido | 20 horas |
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas |
|---|---|---|
| Autómatas de pila: definición | Definición informal y formal de un autómata de pila | * Lectura de las páginas 235-244
|
| Lenguajes aceptados por un autómata de pila | Se tratan dos tipos de reconocimientos: El reconocimiento por pila vacía y el reconocimiento por estado final | * Lectura de las páginas 245-248
|
[editar] Capitulo 5 Lenguajes Independientes de Contexto
[editar] Datos Generales
| Texto Base | Introducción a la teoría de autómatas, lenguajes y computación | ||
| Capitulo | 5. Gramáticas independientes de contexto | ||
| Páginas | 181 - 234 | Horas de estudio empleadas para el desarrollo del contenido | 15 horas |
| Capítulo del libro | 7. Propiedades de los lenguajes independientes de contexto | ||
| Paginas | 273-326 | Horas de estudio empleadas para el desarrollo del contenido | 10 Horas |
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas |
|---|---|---|
| Gramáticas independientes de contexto GIC | Qué es una GIC? | * Lectura de las páginas 181-185
|
| Derivaciones | Se detalla que es una derivación y como se procede para derivar por izquierda y por derecha | * Lectura de las páginas 185-190
|
| Árboles de derivación | Construcción de árboles de derivación | * Lectura de las páginas 194-206
|
| Aplicaciones de las GIC | Analizadores, lenguajes de marcado, XML y su relación con las GIC | * Lectura de las páginas 2006-220
|
| Ambigüedad | Cuándo una gramática es ambigua, efectos de la ambigüedad en los lenguajes, eliminación de la ambigüedad | * Lectura de las páginas 221-233
|
| Formas Normales | Requisitos que debe cumplir una gramática para estar expresada en forma normal | * Lectura de las páginas 273-293
|
[editar] Capitulo 6 Maquinas de Turing
[editar] Datos Generales
| Texto Base | Introducción a la teoría de autómatas, lenguajes y computación | ||
| Capitulo | 8. Introducción a las máquinas de turing | ||
| Páginas | 327 - 396 | Horas de estudio empleadas para el desarrollo del contenido | 15 horas |
| Tema a revisar | Descripción del Contenido a revisar | Actividades Recomendadas |
|---|---|---|
| Notación para la máquina de turing | Se describen los elementos y operaciones de una máquina de turing | * Leer detenidamente las páginas 340-341 y determinar los elementos de una máquina de turing
|
| Diseño de máquinas de turing | Se presenta un ejemplo de diseño de una máquina de turing | * Revise el ejemplo 8.2 de la página 344, la figura 8.9 es la máquina de turing resultante, ejecute la corrida de esta máquina para las cadenas “01”, “0011” y “000111”
|
| Diagramas de transición para las máquinas turing | Un diagrama de transición es otra forma de representar una máquina de turing | * Lea las páginas 346-349
|
[editar] Construcción de máquinas de turing
A continuación se presentan ejemplos de construcción de máquinas de turing: Escriba una máquina de Turín que reconozca cadenas de unos y ceros alternados que siempre inicien en uno y siempre terminen en cero (01)+
La recomendación está en iniciar definiendo la función de trancisión, luego se pueden definir los elementos restantes de la máquina:
La maquina siempre inicia en el estado q0, y la cadena que reconoce, siempre inicia con 0:
| (q0, vacio) = (q1, vacio, D) | Inicio del trabajo de la máquina |
| (q1, 0) = (q2, 0, D) | Inicia reconociendo el cero de la cadena, lo escribe en la cinta y se mueve hacia la derecha |
| (q2, 1) = (q1, 1, D) | Cuando encuentra un uno, regresa al estado q1 para volver a reconocer un cero |
| (q1, blanco) = (q3, blanco, I) | En el estado q1 puede encontrar el símbolo en blanco que indica que la cadena se termino, en ese caso regresa una posición y se mueve al estado 3 en donde se reconoce la cadena. |
| Note que en el estado q1 puede reconocer un cero lo que indica que la cadena continua o puede encontrar un símbolo en blanco lo que indica que la cadena termina |
Ahora definimos los elementos restantes de la máquina:
Estados = {q0, q1, q2, q3}
Alfabeto de la cinta = {0,1, blanco}
Alfabeto = {0,1,}
Estado inicial = {q0}
Estado final = {q3}
Diseñemos ahora una máquina que acepte comentarios en lenguaje c, recuerde que los comentarios en lenguaje c son de este tipo:
/* Aquí va el comentario */
El contenido del comentario puede ser cualquier símbolo, al que llamaremos c
Este símbolo no puede ser el “*”
Igualmente definamos primero la función de transición:
| (q0, vacio) = (q1, vacio, D) | Inicio del trabajo de la máquina |
| (q0, vacio) = (q1, vacio, D) | Inicio del trabajo de la máquina |
| (q1, /) = (q2, /, D) | Inicia reconociendo el “/” de la cadena, lo escribe en la cinta y se mueve hacia la derecha |
| (q2, *) = (q3, *, D) | Cuando encuentra un *, avanza para seguir el reconocimiento |
| (q3,c) = (q3, c, D) | En el estado q3 puede estar leyendo muchos símbolos cualquiera a excepción del * |
| (q3,*) = (q4, *, D) | Cuando en el estado q3 encuentra un *, se prepara para a continuación recibir un / |
| (q4,/) = (q5, /, D) | Cuando en q4 recibe un /, se prepara para terminar de reconocer la cadena |
| (q5, blanco) = (q6, blanco, I) | En el estado q5 puede encontrar el símbolo en blanco que indica que la cadena se termino. |
Ahora si completamos la máquina
Estados = {q0, q1, q2, q3,q4,q5,q6}
Alfabeto de la cinta = {/,*,c,blanco}
Alfabeto = {/.*,c}
Estado inicial = {q0}
Estado final = {q6}
JC T/mc-16-02-07-39
