dfa-python

Código para construir autómatas finitos deterministas en python. Adaptado del original de Vijaya Gajanan.

La operación es interactiva, pidiendo los estados, el alfabeto, estado de enrada y estados de salida, al igual que la tabla de transiciones.

Autómata Finito Determinista (DFA).

Da la lista de estados separados por espacio:

Introduce los nombres de los estados, por ejemplo: q0 q1 q2 (presiona enter)

Al no poner los espacios el programa lo interpretará como un único estado.

Estados : ['q0', 'q1', 'q2']

Da el alfabeto de entrada separado por espacios:

De la misma manera introduce los símbolos del alfabeto, por ejemplo: 0 1

Alfabeto : ['0', '1']

Da la transición para el estado q0. De ser necesario, usa 'RECHAZO'.

ESTADO ACTUAL : q0 ALFABETO DE ENTRADA : 0 SIGUIENTE ESTADO :

Introduce el estado siguiente a partir del estado q0 al leer un '0'. Este proceso se repite para todos los estados y todos los símbolos del alfabeto. El programa no cuenta con un proceso para confirmar que los estados dados estén en la lista, es algo que debe mejorarse. De dar estados fuera del conjunto hasta el final aparecerá un error.

A partir de los valores dados se construye la tabla de transiciones:

FUNCIÓN DE TRANSICIÓN Q X SIGMA -> Q

ESTADO ACTUAL     ALFABETO DE ENTRADA     PRÓXIMO ESTADO

q0      0      q1

q0      1      q0

q1      0      q2

q1      1      q2

q2      0      q1

q2      1      q0

Enseguida se pide el estado inicial, como es un autómata finito determinista recuerda que sólo acepta un estado inicial.

Da el estado inicial:

Posteriormente pedirá los estados finales.

Da el o los estados de aceptación (separados por espacio):

Una vez introducidos revisará que los estados proporcionados estén en la lista de estados dado, de no ser así volverá a pedir el estado inicial y el o los de salida.

Si los estados están en el conjunto se pide elegir la opción:

Elige la opción:

1. Correr el DFA con la cadena de entrada

2. Cambiar el DFA

3. Salir

Para correr el autómata dado se elige la opción 1, la opción 2 en caso de haber cometido un error permite definir de nuevo el autómata (desde cero), para no hacer nada más y salir se elige la opción 3 (por supuesto que en cualquier momento del proceso se puede hacer Ctrl-c).

Da Opción : 1

Da la cadena de entrada : 1001

ESTADO ACTUAL : q0 SÍMBOLO DE ENTRADA : 1 PRÓXIMO ESTADO : q0

ESTADO ACTUAL : q0 SÍMBOLO DE ENTRADA : 0 PRÓXIMO ESTADO : q1

ESTADO ACTUAL : q1 SÍMBOLO DE ENTRADA : 0 PRÓXIMO ESTADO : q2

ESTADO ACTUAL : q2 SÍMBOLO DE ENTRADA : 1 PRÓXIMO ESTADO : q0

Al final aparecerá la palabra ACEPTADA o RECHAZADA de acuerdo a si se llega a un estado de aceptación o uno de rechazo.

Hay detalles por mejorar, no he probado que pasa al dar el estado como rechazo. Tomen la idea y adáptenla a su gusto y necesidades.