Sesion 5

Escuela de Ingeniería de
Sistemas
CURSO: TEORÍA DE LENGUALES Y

COMPILADORES
Sesión 5:
Gramáticas regulares (GR)
Autómatas.
Gramáticas Equivalentes.
Arboles de derivación.
MG. JULISSA REYNA GONZÁLEZ

EMAIL: [email protected]
GRAMÁTICAS
Resumen
Tipo 3
Tipo 3
Gramáticas Regulares
Gramáticas Equivalentes
Árboles de derivación
Ejemplo:
Ejemplo:
Ejemplo:
Ejemplo:
Sub Árboles de derivación
Sub Árboles de derivación
Ambigüedad
Ambigüedad
Ambigüedad
Ambigüedad
Ambigüedad
Ambigüedad
Ambigüedad
Ejercicios (1)
EJERCICIO RESUELTO
EJERCICIOS(2)
1. Se desea diseñar un dispositivo que, dada una cadena
formada por números binarios, encuentre las ocurrencias de la
palabra clave 1011 y sirva de base para un recuento de sus
apariciones. Nótese que si la cadena fuera, por ejemplo,
0101011011011, se detectaría dos ocurrencias de la palabra
clave (subrayadas), no considerando el “1” de la séptima
posición como inicio de otra ocurrencia. Se pide construir el
Autómata Finito Determinista correspondiente.
SOLUCIÓN
1. El objetivo es detectar la palabra clave 1011, tantas veces
como aparezca en la secuencia de entrada de números
binarios. Por lo tanto, el autómata finito deberá llegar a un
estado final cada vez que detecte una ocurrencia de dicha
palabra clave, por lo que no puede quedarse en el estado
final tras encontrar la primera secuencia 1011, si sigue
habiendo números detrás.
SOLUCIÓN
Todo AFD está compuesto por una quíntupla: AFD=(Σ, Q, f, q0,
{F}) • El alfabeto de entrada, en este caso es sencillo, pues
sólo contiene los dígitos 0 y 1 que forman los binarios:
AFD=({0,1}, …) • El conjunto de estados Q se irá definiendo
más adelante en función de las transiciones necesarias, pero
al menos necesitaremos un estado inicial, p, y un estado final,
t, que ya podemos añadir al conjunto: AFD=({0,1}, {p, t, …},…)
• La función de transición, f, la representaremos más adelante
mediante un diagrama de transiciones: AFD=({0,1}, {p, t, …}, f,
…) • El estado inicial ya está definido, denominándose p:
AFD=({0,1}, {p, t, …}, f, p, …)
Por último, el conjunto de estados finales se completará al
final, pero al menos podemos incluir el que ya hemos definido,
llamado t: AFD=({0,1}, {p, t, …}, f, p, {t, …}) Por lo tanto, nos
falta definir el diagrama de transiciones que representa a f,
que también nos permitirá completar el conjunto de estados y
de estados finales.
SOLUCIÓN
Dado que la palabra clave está formada por 4 símbolos, que
deben aparecer siempre de forma consecutiva,
necesitaremos un estado diferente para reconocer cada
subsecuencia de símbolos leídos de la cadena. Es decir,
tendremos un estado (q) para determinar que se ha leído la
subsecuencia “1”, otro estado (r) para indicar la lectura de la
subsecuencia “10”, un estado más (s) para representar el
reconocimiento de la subsecuencia con 3 elementos “101”, y
por último se alcanza el estado final (t) cuando se ha leído la
secuencia completa “1011” de forma consecutiva. Así, de
momento, nos quedaría el siguiente diagrama de transciones:
SOLUCIÓN
SOLUCIÓN
EJERCICIO
2. . En algunos lenguajes de programación, los comentarios
aparecen entre los delimitadores “/*” y “*/” como marca
inicial y final del comentario. Sea L el lenguaje de todas las
cadenas de comentarios delimitados. Así pues todo elemento
de L, empieza por /* y acaba por */, pero no debe tener
ningún */ intermedio. Por simplicidad consideraremos que el
alfabeto sería {a, b, /,*}. Indicar el Autómata Finito
Determinista que reconoce L.
Un posible autómata es AFD1=({/,*,a,b},{S,A,B,C,D,Z},f,S,{D}),
siendo f:
SOLUCIÓN
SOLUCIÓN
 En esta solución, la cadena de entrada debe contener la
marca de inicio de comentario (“\*”) desde el principio, lo
cual se reconoce en las transiciones entre los estados S, A y B.
Si la cadena de entrada no comienza con “\*”, la palabra se
rechaza, transitando desde S o A al estado sumidero, Z.
Además, en esta solución sólo se reconoce un comentario,
por lo que al llegar al final del comentario, es decir, cuando el
autómata está situado en el estado final D, el resto de cadena
no se analiza, dado que se transita al estado sumidero Z, del
que no se sale. Cabe destacar que las transiciones de B, C y
entre ellos leen el texto que se encuentra dentro del
comentario, analizando si se ha llegado a la marca de fin de
comentario (“*/”) o no, y hay que retroceder a B para seguir
leyendo símbolos del interior del comentario.
OTRA SOLUCIÓN
 Otra posible autómata es AFD2=({/,*,a,b},{S,A,B,C,D},f’,S,D),
siendo f’:
EJERCICIOS (3)
EJERCICIOS
EJERCICIOS
EJERCICIOS
EJERCICIOS
ACTIVIDAD ASINCRONICA
ACTIVIDAD ASINCRONICA:
Desarrollo del Taller de
ejercicios.
Referencias
 [1] Aho A., Lam M., Sethi R.., Ullman J. (2008). Compiladores,
Principios, Técnicas y herramientas. Adisson-Wesley.
 [2] Brookshear J. (1989). Teoría de la computación, lenguajes
formales, autómatas y complejidad. Adisson-Wesley.
Wilmington Delaware EUA.

Sesion 5

Cargado por

Copyright:

Formatos disponibles

Sesion 5

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Sesion 5

Cargado por

Copyright:

Formatos disponibles

Escuela de Ingeniería de

CURSO: TEORÍA DE LENGUALES Y

MG. JULISSA REYNA GONZÁLEZ

También podría gustarte