Automatas

Instituto Politécnico Nacional Escuela Superior de Cómputo Ingeniería en Sistemas Computacionales

Teoría Computacional
Ejercicios 04: Programación de un AFD en C

Profesor: Edgardo AdriánFranco Martínez

Alumno: Barradas Spezzia Alberto

Grupo: 2CM1

Fecha de Entrega 14 de octubre de 2011

Alberto Barradas Spezzia • • •

2CM2 Teoría Computacional

Para los ejercicios 03, tomarsu AFD y crear un programa en C que lo implemente. Realizar 5 pruebas y reporte de resultados para cada AFD. Mostrar especificación del AFD y su correspondiente código en C.

Implementación en CPara implementar un autómata en el lenguaje de programación C, basta con realizar un switch-case para los estados y dentro de cada caso comprobar los símbolos para así especificar el estado al cualcambia mediante la transición. Todo esto iterándolo sobre la cadena a analizar. Pero esto se puede generalizar, y es por esto que decidí crear una estructura AFD para trabajar sobre ellaindependientemente de los estados, símbolos, transiciones, posición inicial y posiciones finales que tenga. Mi estructura AFD queda definida de la siguiente manera:
typedef struct { char* sims; char* edos;transicion* trans; int inicial; int* finales; } AFD; // // // // // Arreglo de Arreglo de Arreglo de Índice del Índices de símbolos (alfabeto) los estados transiciones estado inicial del autómata los estadosfinales

Como se puede apreciar, construí también una estructura para definir las transiciones:
typedef struct { int ini; int fin; char simbolo; } transicion; // Índice del Origen o Estado inicial //Índice del Destino o Estado final // Simbolo de la transición

Estas estructuras son sobre las que realizo la comprobación de la cadena para un autómata dado, esto lo hago por medio de la siguientefunción:
int prove(char* cadena, AFD autom){ int i,t; // Índices para iterar sobre la cadena y transiciones. int edoAct = autom.inicial; // Estado en el que se encuentra. // Número total de...