[C con Clase] Programa Automata Finito Determinista

[Steven Davidson]

Hola Isauro,

El pasado 2007-05-18 15:35:14, isauro escribió:

i> Hola amigos buenos dias.
i> el motivo de este correo es para pedirles ayuda para hacer este programa de DFA ya que la verdad no lo he pidido hacer, basicamente es por que no entiendo bien aun lo que son las transiciones de un DFA asi que si alguien me pudiera orientar sobre como poder programarlo o alguna ayuda para saver como manejar las trancisiones.

Veamos. Un autómata finito consiste de tres cosas:

1. Un conjunto finito de estados, el cual uno es designado el estado inicial, y algunos (o quizá ninguno) son designados los estados finales.

2. Un abecedario de posible letras o símbolos entrantes, de los cuales se forman cadenas, que serán leídos uno a uno.

3. Un conjunto finito de transiciones que indican para cada estado y para cada letra del abecedario entrante cuál estado pasa al siguiente.

Por lo que nos dices, no tienes problemas con los dos primeros conceptos. El tercer concepto tiene que ver con una serie de transiciones a modo de reglas o axiomas. Estas transiciones sirven para indicar la lógica del AF. Pasamos de un estado a otro siguiendo la lógica establecida por esta lista de transiciones. Para facilitar la legibilidad de estas reglas, creamos una table de transiciones. Por ejemplo, tenemos un AF en particular.

El lenguaje de este AF se define con la siguiente expresión regular:

(a + b)b*

O sea, este lenguaje describe cadenas que empiezan por 'a' ó 'b' y pueden terminar con una serie de 'b'. Por ejemplo, "a", "b", "abbbbb", "bbbbbbbbbbbb", etc..

Ahora vamos a describir esta expresión como una serie de estados y axiomas para pasar de un estado a otro. En nuestro ejemplo, vamos a crear dos estados {x,y}, por lo que los axiomas pueden ser:

1. Del estado 'x' con la entrada 'a' pasamos al estado 'y'.
2. Del estado 'x' con la entrada 'b' pasamos al estado 'y'.
3. Del estado 'y' con la entrada 'b' pasamos al estado 'y'.

Esto se ve mejor con una tabla:

Estados \ Abecedario |  a  |  b
---------------------+-----+-----
Estado inicial: x    |  y  |  y
Estado final:   y    |  -  |  y

También podemos ver mejor la lógica de estas tansiciones con un diagrama. Esto es,

+----+
| x- |
+----+
 |  |
 |  |
a|  |b
 |  |
 V  V
+----+
| y+ |
+----+
 |   ^
 | b |
 +---+

El menos (-) indica el estado inicial y el más (+) es el estado final.


Implementando un AF puede ser comprobar dicha tabla previamente diseñada y creada. Debido a la "naturaleza" de la programación, podemos usar números enteros en lugar de letras para los estados. En cuanto al alfabeto, no podemos cambiar las letras, porque pertenecen al lenguaje. Lo que sí podemos hacer es crear una cadena para describir tal abecedario y usar números enteros como índices para la tabla. Al final, para describir las transiciones, tenemos lo siguiente:

char abecedario[2] = { 'a', 'b' };
unsigned int estados[2];  // x = 0, y = 1

unsigned int transiciones[2][2] = { { 1,1},  // De 'x' a ...
                                    {-1,1},  // De 'y' a ...

Como puedes ver, tenemos que describir la posibilidad de que no exista una transición de un estado a otro. He elegido usar el valor -1 para indicar este caso.

También podríamos haber definido un tipo enumerado para los estados y usar las constantes 'X' e 'Y' en lugar de números enteros.

Para determinar la transición que nos toca, tenemos una letra entrante que tenemos que convertir a un número entero (como índice). También sabemos el estado actual en que nos encontramos y por tanto su índice. Ahora nos queda aplicar estos dos índices en nuestra tabla 'transiciones' para averiguar el nuevo estado. Esto es,

unsigned int estado_actual;
char letra;
...
unsigned int temp;

temp = transiciones[ estado_actual ][ buscar(letra,abecedario) ];

if( -1 == temp )  // ¿Error lingüístico?
{
  // Detener el AF
  ...
}
else
{
  // Hacemos la transición del estado actual al nuevo
  estado_actual = temp;
}

En el código anterior, uso la función 'buscar()'. Esto significa que tendrás que buscar el índice de 'abecedario' que corresponda con la letra entrante, 'letra'.


Hay varias maneras de hacer todo esto, pero espero que esto te sirva de guía.

Steven