GUIA DE EJERCICIOS AFND Y AFD





UNIVERSIDAD NACIONAL AUTONOMA DE HONDURAS
EJERCICIOS PRACTICOS DEL I PARCIAL
LENGUAJES DE PROGRAMACION
AFND Y AFD



1. Se desea diseñar un dispositivo que, dada una cadena formada por númerosbinarios, 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 dosocurrencias 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.

2.- Identifiqueotro autómata finito determinista de la vida diaria y dibuje su diagrama de transiciones.
Un bolígrafo. Las entradas posibles al sistema son: x1=pulsar ó x2= no pulsar. La respuesta ante una mismaentrada no siempre es la misma. Depende también de la historia de las entradas anteriores. Dicha historia de entradas anteriores se resume diciendo que el sistema está en un estado dado. Todo lo que puedepasar en la vida útil de un bolígrafo es que su punta esté dentro o esté fuera. La respuesta depende de la entrada aplicada y de si está dentro o fuera. Además, en la definición de autómata finitodebe haber un estado inicial. Podemos elegir un bolígrafo que inicialmente tuviera la punta dentro.

Solución:


3.- Utilizando métodos intuitivos y razonamiento lógico, modifique el diagrama detransiciones de la siguiente figura (fig. 1.17) para que acepte las mismas cadenas que antes, pero ahora sin ramificaciones no deterministas.




Solución:
Acepta dos clases de cadenas:
1ª: (dígito)n(punto) (dígito)m, m, n >= 1
2ª: (dígito)r r >= 1

La primera clase podría reducirse a la segunda, si modificamos el diagrama original de forma que el estado al que llega tras (dígito)n, (el 2) sea deaceptación.

Diagramar el estado final AFD.

4.- Dibuje un diagrama de transiciones que acepte la unión de los lenguajes aceptados por los siguientes diagramas:





Solución:
Lenguajes generados:
a)...