Taller De Programacion

TALLER DE PROGRAMACIÓN No. 1 – RECONOCIMIENTO DE CADENAS POR MEDIO DE UN AFD

OBJETIVO:

Construir un programa que permita al usuario ingresar la especificación de un autómata finito determinístico (AFD) y reconocer cadenas a partir de él.

ENUNCIADO:

Construir un programa, en cualquier lenguaje de programación, que permita al usuario ingresar todas las especificaciones de un AFD:

1. Alfabeto

2. Estados del autómata, estado inicial y conjunto de estados finales

3. Tabla de transiciones del autómata

Luego el programa debe solicitar al usuario ingresar cadenas y realizar el reconocimiento:

1. El programa debe permitir ingresar cualquier cantidad de cadenas, mientras el usuario desee.

2. Para cada cadena, debe mostrar la secuencia de reconocimiento y al final, si fue reconocida o no.

3. En caso de no ser reconocida, debe mostrar el error.

ENTREGABLES:

Este taller puede ser realizado en grupos de máximo tres personas y deben entregar:

1. El programa fuente, el cual puede ser realizado en cualquier lenguaje de programación (C, Java, Visual Basic, PHP…)

2. Un documento (Digital, en Word o pdf) que debe contener:

a. Descripción de las estructuras de datos utilizadas, incluyendo diagramas (Vectores, matrices, listas…)

b. Descripción de la implementación de los métodos de reconocimiento

Estructura de Datos

Para realizar la aplicación utilizaremos la siguiente estructura de datos, se creara una matriz de n*n que nos permitirá capturar los valores de las transiciones asociadas a la quíntupla, donde cada columna representa la etiqueta y una transición y las filas al estado al cual se llega mediante esa etiqueta.

M = {∑, S, S_0, F, δ }

Los distintos estados estarán dentro de una cadena de caracteres separado por comas, donde cada estado es representado de la siguiente manera:

A+ = estado inicial del Autómata.

B = estado del autómata

C* = Estado Final del Autómata.

Esta cadena se obtendrá a través de la interfaz del usuario.

Para obtener ∑ utilizaremos una cadena donde cada símbolo estará separada por coma",".

Por último, a través de una interfaz dinámica obteniendo el alfabeto y los distintos estados el usuario seleccionara cada transición de distintos estados.

...