Alchitex

0

Mi primer AFD [ES]

lunes, 4 de abril de 2011 | Author: Alex Alvarez Gárciga | Etiquetas: Java, Programación, Teoría

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.

La definición formal y los conceptos de autómata finito y sistema determinista pueden buscarlos en la  Wikipedia ya que no es mi objetivo explicar aquí tales conocimientos, además no creo que sea el más capacitado para ello.

Pero lo cierto es que estudiando para la asignatura de "Compiladores" me he topado con esta herramienta que ahora veo que me será útil, de seguro, más de una vez.

Ya para ir entrando en calor, quiero comentar sobre mi primer trastazo con esto de lo que les hablaba.

Resulta ser de un ejercicio donde me piden asegurar que una cadena de texto cumpla con las siguientes condiciones: siendo así la primera, que mi alfabeto válido está compuesto solo por el conjunto de estos símbolos (a, b, c, d), cumpliéndose obligatoriamente que la cantidad válida para los símbolos a y b deben ser pares, mientras que los restantes c y d pueden ser usados sin restricción alguna. 

1. cd
2. acda
3. abab
4. aaccdbaba

Para resolver tal problema mi AFD ha quedado como sigue:
Un poco feo, pero espero que les llegue a todos la idea.

Después solo restó programarlo, que para el caso me auxilie de Java como lenguaje. Aquí les dejo la clase AFD que implementa este autómata:

package afdexample;

/**
 *
 * @author Alex Alvarez Garciga
 */
enum Status {q0, q1, q2, q3}

public class AFD {

    public Boolean Check(String text){
        Status _status = Status.q0;
        for (int i = 0; i < text.length(); i++) {

            switch(_status){
                case q0:
                        switch(text.charAt(i)){
                            case 'c':
                            case 'd':
                                    _status = Status.q0;
                                break;
                            case 'a':
                                    _status = Status.q1;
                                break;
                            case 'b':
                                    _status = Status.q2;
                                break;
                            default:
                                return false;
                        }
                    break;
                case q1:
                        switch(text.charAt(i)){
                            case 'c':
                            case 'd':
                                    _status = Status.q1;
                                break;
                            case 'a':
                                    _status = Status.q0;
                                break;
                            case 'b':
                                    _status = Status.q3;
                                break;
                            default:
                                return false;
                        }
                    break;
                case q2:
                        switch(text.charAt(i)){
                            case 'c':
                            case 'd':
                                    _status = Status.q2;
                                break;
                            case 'a':
                                    _status = Status.q3;
                                break;
                            case 'b':
                                    _status = Status.q0;
                                break;
                            default:
                                return false;
                        }
                    break;
                case q3:
                        switch(text.charAt(i)){
                            case 'c':
                            case 'd':
                                    _status = Status.q3;
                                break;
                            case 'a':
                                    _status = Status.q2;
                                break;
                            case 'b':
                                    _status = Status.q1;
                                break;
                            default:
                                return false;
                        }
                    break;
            }
        }
        return _status == Status.q0;
    }
}