Autómatas Finitos Deterministas y No Deterministas Equivalentes en Java

Contenido

  • ¿Qué es un autómata y para qué sirve?
  • Definición formal de un AFD y AFND
  • Diferencia entre un AFD y AFND
  • Equivalencia entre autómatas
  • Algoritmo en Java

¿Qué es un autómata y para qué sirve?

Un autómata finito es un modelo matemático en forma de grafo dirigido surgido en los años 30 y 40 a partir de grandes matemáticos como Church y Turing para el estudio de lo que a la postre se llamaría ‘Teoría de la Computabilidad’.

Un autómata esta formado por un conjunto de vértices llamados estados y aristas llamadas transiciones. Un autómata se encuentra inicialmente en un estado llamado estado inicial. El autómata cuando recibe una palabra o secuencia de caracteres de entrada, se mueve a través de las transiciones para cambiar su estado. Los autómatas se clasifican según el número de estados, la forma en que se realiza el cambio de estado, si acepta o no el símbolo vacío, si tiene una pila, etc.

Una de las aplicaciones de los autómatas más comunes son las expresiones regulares y lenguajes formales porque está estrechamente relacionados con los autómatas finitos deterministas y pueden considerarse una alternativa de forma que el usuario pueda comprender fácilmente la notación de los AFND (Autómatas Finitos No Deterministas).

Definición formal de un AFD y AFND

Un autómata finito determinista (AFD) es una quíntupla

M = (\Sigma, Q, \delta, q_{0}, F)

donde:

  • \Sigma es un alfabeto
  • Q es un conjunto no vacío de estados
  • \delta representa la función de transición
\delta : Q \times \Sigma \longrightarrow Q ; \quad \delta(q, \sigma) = p
  • q_{0} \in Q es el estado inicial
  • F \subset Q es el conjunto de estados finales que son los que provocan la parada del autómata

Para representar un AFD y AFND se utiliza una gráfica dirigida donde los vértices representan los estados y las aristas la función de transición representada de la siguiente forma

\delta(q_i, x) = q_j

La función de transición devuelve el siguiente estado q_j que el autómata tendrá dado el estado en el que se encuentra q_i con una entrada dada x . Por ejemplo:

Autómata Finito No Determinista

La función de transición extendida permite obtener todos los estados dada una cadena de entrada y puede definirse como sigue:

\hat{\delta}(q_i, w) = \{ q_0, q_1, …, q_j \}

esta definición es importante para conocer la definición del lenguaje que acepta un autómata finito determinista que se expresa de la siguiente forma:

L(M) = \{ w | \hat{\delta}(q_0, w) = F \}

y se lee el lenguaje de un autómata M dado un conjunto de palabras w tal que la función de transición extendida \hat{\delta} desde q_0 da un resultado que pertenece al conjunto de estados finales F.

La definición de lenguaje de un autómata finito no determinista es de la siguiente forma.

L(M) = \{ w | \hat{\delta}(q_0, w) \cap F \neq \varnothing \}

Diferencia entre un AFD y AFND

Mientras que en un AFND existe más de una transición \delta(q_i,x) para los estados de un autómata q \in Q dado un subconjunto de símbolos x \in \Sigma sin embargo en un AFD para cada estado que se encuentre el autómata y con cualquier símbolo del alfabeto leído, existe no más de una transición posible desde ese estado y con ese símbolo.

Equivalencia entre autómatas

Dos autómatas M_1 y M_2 son equivalentes si aceptan el mismo lenguaje, M_1 \equiv M_2 si L(M_1) \equiv L(M_2)

  • Si eliminamos todos los estados no accesibles (o aislados) de un autómata, obtenemos un autómata equivalente al autómata original
  • Obviamente tal autómata se representa con un grafo conexo

Algoritmo en Java

El algoritmo es Java que desarrolle para obtener equivalencias entre autómatas finitos no deterministas y autómatas finitos deterministas es el siguiente:

import java.util.*;

public class ConverterAFD {

    private List<Set<Integer>> visited = new LinkedList<>();

    private Stack<Set<Integer>> stack = new Stack<>();

    private Graph<Integer, Pair<Integer, String>> input;

    public ConverterAFD(Graph<Integer, Pair<Integer, String>> input) {
        this.input = input;
    }

    public Graph run(int initialNode) {
        Map<Set<Integer>, Map<String, Set<Integer>>> table = this.buildTable(initialNode);
        Graph output = this.createGraphFromTable(table);
        return output;
    }

    public Map<Set<Integer>, Map<String, Set<Integer>>> buildTable(int initialNode) {
        Map<String, Set<Integer>> m1 = null;
        Map<Set<Integer>, Map<String, Set<Integer>>> table = new HashMap<>();

        Set<Integer> node = Utils.createSetOf(initialNode), s1 = null, s2 = null, s3 = null;
        stack.add(node);

        while (!queue.isEmpty()) {
            s1 = stack.pop();

            m1 = new HashMap<>();
            for (int i1 : s1) {
                Iterable<Pair<Integer, String>> edges = this.input.adj(i1);

                for (Pair<Integer, String> edge : edges) {

                    if (edge == null) {
                        continue;
                    }

                    String key = edge.edge;
                    int value = edge.vertex;

                    if (m1.containsKey(key)) {
                        s2 = m1.get(key);
                        s2.add(value);
                    } else {
                        s2 = Utils.createSetOf(value);
                    }
                    m1.put(key, s2);
                }
            }

            for (String key : m1.keySet()) {
                s3 = m1.get(key);
                if (!visited.contains(s3)) {
                    queue.add(s3);
                    visited.add(s3);
                }
            }


            table.put(s1, m1);
        }

        return table;
    }

    private Graph<Set<Integer>, Pair<Set<Integer>, String>> createGraphFromTable(Map<Set<Integer>, Map<String, Set<Integer>>> table) {
        int size = table.size();
        Graph<Set<Integer>, Pair<Set<Integer>, String>> output = new Graph<>(size);

        for (Set<Integer> key : table.keySet()) {
            Map<String, Set<Integer>> value = table.get(key);

            for (String keyValue : value.keySet()) {
                Set<Integer> valueValue = value.get(keyValue);
                output.addEdge(key, new Pair<>(keyValue, valueValue));
            }
        }

        return output;
    }
}

En la clase ConverterAFD utilizamos DFS para movernos a través del autómata e iteramos primero a través de cada elemento del estado que se forma cuando convertimos un AFND a AFD e iteramos a través de cada arista para obtener la unión de estados y agruparlos.

La clase ConverterAFD acepta una clase de tipo Graph en el constructor que esta definida en el siguiente bloque de código.

import java.util.*;
import java.util.List;

public class Graph<V, E extends Pair> {

    private final int V;

    private int E;

    private List<E>[] adj;

    private List<V> vertex;

    public Graph(int V) {
        this.V = V;
        this.E = 0;

        this.adj = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            this.adj[i] = new LinkedList<>();
        }

        this.vertex = new LinkedList<>();
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(V m, E n) {
        if (!this.vertex.contains(m)) {
            this.vertex.add(m);
        }
        int index = this.vertex.indexOf(m);
        this.adj[index].add(n);
        this.E++;
    }

    public Iterable<E> adj(V m) {
        int index = this.vertex.indexOf(m);
        return this.adj[index];
    }

    public GraphIterator iterator() {
        return new GraphIterator();
    }

    private class GraphIterator implements Iterator<Pair<V, List<E>>> {

        private int indexV = 0;


        @Override
        public boolean hasNext() {
            return indexV < Graph.this.V;
        }

        @Override
        public Pair<V, List<E>> next() {
            V vertex = Graph.this.vertex.get(indexV);
            List<E> element = Graph.this.adj[indexV];

            this.indexV++;

            return new Pair<>(element, vertex);
        }
    }
}
public class Pair<V, E> {

    public E edge;

    public V vertex;

    public Pair(E edge, V vertex) {
        this.edge = edge;
        this.vertex = vertex;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();

        builder.append(edge);
        builder.append(", ");
        builder.append(vertex);

        return builder.toString();
    }

    public static <E, V> Pair of(E edge, V vertex) {
        return new Pair(edge, vertex);
    }
}

Finalmente Creamos una clase para imprimir los autómatas en una imagen.

public class PrintGraph {

    public void printWithSet(org.oaksoft.automatas.graph.Graph<Set<Integer>, Pair<Set<Integer>, String>> input, String name, File output, Format format) throws IOException {

        List<LinkSource> sourceList = new ArrayList<>();
        for (Iterator it = input.iterator(); it.hasNext(); ) {
            Pair pair = (Pair) it.next();

            Node source = node(Utils.printLabelNode((Set<Integer>) pair.vertex));
            List edges = (List) pair.edge;

            for (int i = 0; i < edges.size(); i++) {
                Pair edgePair = (Pair) edges.get(i);

                Node sink = node(Utils.printLabelNode((Set<Integer>) edgePair.vertex));

                sourceList.add(
                        source.link(
                                to(
                                        sink
                                ).with(Label.of((String) edgePair.edge))
                        )
                );
            }
        }

        Graph graph = graph(name).directed().with(sourceList);
        Graphviz.fromGraph(graph).width(800).height(1300).render(format).toFile(output);
    }
}

y finalmente una clase utilitaria que nos ayuda a generar colocar código que no pertenece a ninguna clase.

import java.util.HashSet;
import java.util.Set;

public class Utils {

    public static <I> Set<I> createSetOf(I... element) {
        Set<I> elements = new HashSet<>();
        for (int i = 0; i < element.length; i++) {
            elements.add(element[i]);
        }
        return elements;
    }

    public static String printLabelNode(Set<Integer> s1) {
        StringBuilder builder = new StringBuilder();
        builder.append("{");
        int i = 0;
        for (Integer i1 : s1) {
            builder.append(i1);
            if (i < s1.size() - 1) {
                builder.append(",");
            }
            i++;
        }
        builder.append("}");

        return  builder.toString();
    }
}

y estas son las dependencias que requiere el código para compilar

        <dependency>
            <groupId>guru.nidi</groupId>
            <artifactId>graphviz-java</artifactId>
            <version>0.16.1</version>
        </dependency>
Autómata Finito Determinista equivalente a la segunda imagen de la entrada

Referencias

http://formella.webs.uvigo.es/doc/talf12/talf_final.pdf
https://es.wikipedia.org/wiki/Aut%C3%B3mata_finito_determinista
https://es.wikipedia.org/wiki/Aut%C3%B3mata_finito_no_determinista

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.