Tarea 3

UNIVERSIDAD NACIONAL
Facultad de Ciencias Exactas y Naturales
Escuela de Informática
EIF400 – Paradigmas de Programación

EIF400 Paradigmas de Programación
Tarea #3
Prof. M.Sc. Georges E. AlfaroS.
PARTE 1.
Construya los diagramas de transición de autómatas de estado finito para reconocer:
1. Hileras formadas por dígitos binarios, que contengan un número de 1s que sea múltiplo de 3.
2.Hileras formadas por caracteres tomados del alfabeto Σ = {𝑎, 𝑏, 𝑐} que se encuentren ordenados
alfabéticamente.
3. Hileras formadas del mismo alfabeto del ejercicio anterior que contengan al menos 3 ‘b’entre cada
par de símbolos ‘a’.
4. Hileras formadas por caracteres alfabéticos (‘a’, ‘b’, .. ‘z’) que contengan la subhilera ‘abc’.
5. Hileras formadas por caracteres alfabéticos que contengan lasubhilera ‘abc’ por lo menos 2 veces
(no necesariamente consecutivas).
6. Hileras formadas por caracteres alfabéticos que NO contengan la subhilera ‘abc’.
7. Números binarios mayores a 24.
Defina encada caso:
Q (el conjunto de estados)
Σ (el alfabeto)
δ (la función de transición (𝛿: 𝑄×Σ ⟶ 𝑄)
q0 (el símbolo inicial)
F (el conjunto de estados finales)
Utilice un diagrama de transiciones e indiquepor aparte la definición de Σ. Muestre ejemplos de aceptación
y rechazo de hileras en cada caso.

PARTE 2
Escriba un programa de consola, utilizando C, C++, Java o C#, para leer la definición de unautómata de
estado finito (FSA) desde un archivo XML. El programa recibirá como parámetro el nombre del archivo y
opcionalmente el nombre de un archivo de texto con las hileras que serán verificadaspor el autómata. Si no
se especifica ningún archivo de datos, el programa leerá y verificará las hileras de manera interactiva.
Incluya la descripción del archivo XML para poder definir nuevosautómatas.
Opcionalmente, puede construir una interfaz gráfica para el programa.
Pruebe el programa con cada uno de los autómatas desarrollados en la primera parte.

2015-2 Tarea #3

pág. 1/1...