AF
Class AF

java.lang.Object
  AF.AFabstracto
      AF.AF

public class AF
extends AFabstracto

Clase para la implementacion interna de un automata finito. La mayoria de sus atributos y metodos son heredados de la superclase abstracta AFabstracto.

Version:

Revision 1.2.2, 16/03/09

Author:

Jesus Vilares ( jvilares@udc.es)

Field Summary

Fields inherited from class AF.AFabstracto

alfabeto, arcos, estados, finales, i, inicial, MAX_ESTADOS

Constructor Summary

AF(java.util.LinkedHashSet qs, java.util.LinkedHashSet ab, Estado i, java.util.LinkedHashSet as, java.util.LinkedHashSet fs)
Constructor directamente heredado de la superclase abstracta (vease AFabstracto.AFabstracto(LinkedHashSet,LinkedHashSet,Estado,LinkedHashSet,LinkedHashSet)).

AF(java.lang.String af)
Constructor directamente heredado de la superclase abstracta (vease AFabstracto.AFabstracto(String)).

Method Summary

private java.util.LinkedHashSet	calc_arcos_min(java.util.ArrayList conjs_qs, java.util.LinkedHashSet alfabeto_min, AF afcnx) Obtener el conjunto de arcos/transiciones del automata minimo
private void	calc_distinguibles(int n, boolean[] tabla, java.util.Hashtable q2i, Estado[] i2q, AF afcnx) Obtiene la matriz de distinguibilidad del algoritmo de minimizacion marcando (i.e. a true) las entradas correspondientes a pares de estados equivalentes.
private int	calc_size(int n) Calcula el tamanho necesario para el array que implementa la matriz de distinguibilidad del algoritmo de minimizacion
AF	determinizar() Devuelve al Automata Finito Determinista (AFD) equivalente a este automata.
java.util.LinkedHashSet	Ecierre(java.util.Collection qs) Calcula el E-cierre de un conjunto de estados dado
java.util.LinkedHashSet	Ecierre(Estado q) Calcula el E-cierre de un estado dado
boolean	es_AFD_no_especificado() Determina si se trata de un Automata Finito Determinista (AFD) pero sin exigir que este completamente especificado.
boolean	es_AFD() Determina si se trata de un Automata Finito Determinista (AFD).
boolean	es_conexo() Determina si se trata de un automata conexo o no.
boolean	es_conexo(java.util.Collection acc, java.util.Collection inacc) Determina si se trata de un automata conexo o no, devolviendo ademas, los conjuntos de estados accesibles e inaccesibles del automata.
private AF	generate_AFD_minimo(int n, boolean[] tabla, java.util.Hashtable q2i, Estado[] i2q, AF afcnx) Construye el automata minimo resultante: ultima parte del proceso de minimizacion
private java.util.ArrayList	get_equivalentes(int n, boolean[] tabla, java.util.Hashtable q2i, Estado[] i2q) Devuelve los conjuntos de estados equivalentes (clases de equivalencia) en base a la matriz de distinguibilidad del algoritmo de minimizacion.
private int	get_xy(int n, int x, int y) Dada una posicion de la matriz de distinguibilidad del algoritmo de minimizacion, calcula el indice correspondiente en el array que lo implementa.
private void	init_distinguibles(int n, boolean[] tabla, java.util.Hashtable q2i, Estado[] i2q, AF afcnx) Inicializa la matriz de distinguibilidad del algoritmo de minimizacion marcando (i.e. a true) las entradas correspondientes a pares (estado final, estado no final).
static AF	loadAF() Carga un AF a partir de la especificacion en formato string almacenada en un fichero de texto.
static AF	loadAF(java.lang.String path) Carga un AF a partir de la especificacion en formato string almacenada en un fichero de texto.
AF	minimizar() Devuelve al Automata Minimo equivalente a este automata.
private void	print_distinguibles(int n, boolean[] matriz, java.util.Hashtable q2i, Estado[] i2q) Imprime la matriz de distinguibilidad.
void	saveAF() Genera y almacena en un fichero de texto la especificacion en formato string del AF.
void	saveAF(java.lang.String path) Genera y almacena en un fichero de texto la especificacion en formato string del AF.
boolean	scan(Cadena cadena) Comprueba si el automata acepta o no una cadena de entrada
private int	search_conj_qs(Estado q, java.util.ArrayList a) Busca el conjunto de estados equivalentes en el que esta almacenado un estado dado.
java.util.LinkedHashSet	siguientes(java.util.Collection qs, Terminal t) Devuelve el conjunto de estados alcanzables desde un conjunto de estado qs consumiendo un terminal t de la entrada.
java.util.LinkedHashSet	siguientes(Estado q, Terminal t) Devuelve el conjunto de estados alcanzables desde un estado q consumiendo un terminal t de la entrada.
AF	subautomata_conexo() Devuelve al subautomata conexo equivalente a este automata.
private boolean	super_es_AFD(boolean estricto) Determina si se trata de un Automata Finito Determinista (AFD), permitiendo exigir o no que este completamente especificado.
private boolean	super_es_conexo(boolean store, java.util.Collection acc, java.util.Collection inacc) Determina si se trata de un automata conexo o no, devolviendo ademas, si se desea, los conjuntos de estados accesibles e inaccesibles del automata.
private boolean	superscan(Cadena cadena, java.util.List l, boolean trace) Comprueba si el automata acepta o no una cadena de entrada, posibilitando obtener la traza de las configuraciones instantaneas por las que pasa
boolean	trace(Cadena cadena, java.util.List l) Comprueba si el automata acepta o no una cadena de entrada, posibilitando obtener la traza de las configuraciones instantaneas por las que pasa
java.util.LinkedHashSet	unidos(java.util.Collection qs, Terminal t) Obtiene el conjunto de estados conectados DIRECTAMENTE con un conjunto de estados dado mediante un terminal determinado.
java.util.LinkedHashSet	unidos(Estado q, Terminal t) Obtiene el conjunto de estados conectados DIRECTAMENTE con un estado dado mediante un terminal determinado.

Methods inherited from class AF.AFabstracto

check_arco, contains_arco, contains_estado, contains_terminal, create_estado, dibujar, esFinal, esInicial, get_tabla_transiciones, getAlfabeto, getArcos, getArcosPpo, getArcosPpoTerminal, getEstados, getFinales, getInicial, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

AF

public AF(java.lang.String af)
   throws AF_Exception,
          G_Exception

Constructor directamente heredado de la superclase abstracta (vease AFabstracto.AFabstracto(String)).

Parameters:

af - Especificacion del automata en formato string.

Throws:

AF_Exception

G_Exception

AF

public AF(java.util.LinkedHashSet qs,
          java.util.LinkedHashSet ab,
          Estado i,
          java.util.LinkedHashSet as,
          java.util.LinkedHashSet fs)
   throws AF_Exception,
          G_Exception

Constructor directamente heredado de la superclase abstracta (vease AFabstracto.AFabstracto(LinkedHashSet,LinkedHashSet,Estado,LinkedHashSet,LinkedHashSet)).

Parameters:

qs - Conjunto de estados del automata

ab - Alfabeto del automata

i - Estado inicial

as - Conjunto de arcos/transiciones del automata

fs - Conjunto de estados finales

Throws:

AF_Exception

G_Exception

Method Detail

loadAF

public static AF loadAF(java.lang.String path)
                 throws java.io.IOException,
                        AF_Exception,
                        G_Exception

Carga un AF a partir de la especificacion en formato string almacenada en un fichero de texto. Las lineas encabezadas por '#' son ignoradas.

Parameters:

path - Path completo al archivo a procesar

Returns:

AF cargado

Throws:

java.io.IOException

AF_Exception

G_Exception

loadAF

public static AF loadAF()
                 throws java.io.IOException,
                        AF_Exception,
                        G_Exception

Carga un AF a partir de la especificacion en formato string almacenada en un fichero de texto. Las lineas encabezadas por '#' son ignoradas. El fichero es seleccionado mediante un cuadro de dialogo.

Returns:

AF cargado

Throws:

java.io.IOException

AF_Exception

G_Exception

saveAF

public void saveAF(java.lang.String path)
            throws java.io.IOException

Genera y almacena en un fichero de texto la especificacion en formato string del AF.

Throws:

java.io.IOException

saveAF

public void saveAF()
            throws java.io.IOException

Genera y almacena en un fichero de texto la especificacion en formato string del AF. El fichero es seleccionado mediante un cuadro de dialogo.

Throws:

java.io.IOException

Ecierre

public java.util.LinkedHashSet Ecierre(Estado q)

Calcula el E-cierre de un estado dado

Parameters:

q - Estado a procesar

Returns:

E-cierre del estado

Ecierre

public java.util.LinkedHashSet Ecierre(java.util.Collection qs)

Calcula el E-cierre de un conjunto de estados dado

Parameters:

qs - Conjunto de estados a procesar

Returns:

E-cierre del conjunto de estados

unidos

public java.util.LinkedHashSet unidos(Estado q,
                                      Terminal t)

Obtiene el conjunto de estados conectados DIRECTAMENTE con un estado dado mediante un terminal determinado. En el caso de que se trate de epsilon, equivale al E-cierre.

Parameters:

q - Estado origen

t - Terminal

Returns:

Conjunto de estados conectados DIRECTAMENTE con q mediante un arco etiquetado con t, o el E-cierre de q en el caso de epsilon

unidos

public java.util.LinkedHashSet unidos(java.util.Collection qs,
                                      Terminal t)

Obtiene el conjunto de estados conectados DIRECTAMENTE con un conjunto de estados dado mediante un terminal determinado. En el caso de que se trate de epsilon, equivale al E-cierre.

Parameters:

qs - Conjunto de estados origen

t - Terminal

Returns:

Conjunto de estados conectados DIRECTAMENTE con algun estado de qs mediante un arco etiquetado con t, o el E-cierre de qs en el caso de epsilon.

siguientes

public java.util.LinkedHashSet siguientes(Estado q,
                                          Terminal t)

Devuelve el conjunto de estados alcanzables desde un estado q consumiendo un terminal t de la entrada. En el caso de que se trate de epsilon, equivale al E-cierre.

Parameters:

q - Estado origen

t - Terminal a consumir

Returns:

Estados alcanzables desde q consumiendo t, o el E-cierre de q en el caso de epsilon

siguientes

public java.util.LinkedHashSet siguientes(java.util.Collection qs,
                                          Terminal t)

Devuelve el conjunto de estados alcanzables desde un conjunto de estado qs consumiendo un terminal t de la entrada. En el caso de que se trate de epsilon, equivale al E-cierre.

Parameters:

qs - Conjunto de estados origen

t - Terminal a consumir

Returns:

Estados alcanzables desde qs consumiendo t o el E-cierre de qs en el caso de epsilon

superscan

private boolean superscan(Cadena cadena,
                          java.util.List l,
                          boolean trace)
                   throws AF_Exception

Comprueba si el automata acepta o no una cadena de entrada, posibilitando obtener la traza de las configuraciones instantaneas por las que pasa

Parameters:

cadena - Cadena a comprobar

l - Lista donde se almacenarian las configuraciones instantaneas. AVISO: la variable debe estar inicializada

trace - Switch indicando si queremos o no tambien obtener la traza

Returns:

true/false segun el automata acepte o no la cadena

Throws:

AF_Exception - Si en el caso del trace la lista de entrada no esta inicializada o vacia

scan

public boolean scan(Cadena cadena)

Comprueba si el automata acepta o no una cadena de entrada

Parameters:

cadena - Cadena a comprobar

Returns:

true/false segun el automata acepte o no la cadena

trace

public boolean trace(Cadena cadena,
                     java.util.List l)
              throws AF_Exception

Comprueba si el automata acepta o no una cadena de entrada, posibilitando obtener la traza de las configuraciones instantaneas por las que pasa

Parameters:

cadena - Cadena a comprobar

l - Lista donde se almacenaran las configuraciones instantaneas. AVISO: la variable debe estar inicializada

Returns:

true/false segun el automata acepte o no la cadena

Throws:

AF_Exception - Si en el caso del trace la lista de entrada no esta inicializada o vacia

super_es_AFD

private boolean super_es_AFD(boolean estricto)

Determina si se trata de un Automata Finito Determinista (AFD), permitiendo exigir o no que este completamente especificado. Es decir, lo aceptaremos si:
(1) para cada combinacion estado-terminal hay EXACTAMENTE/A LO SUMO 1 transicion (dependiendo de si queremos ser estrictos o no)
(2) NO tiene E-transiciones

Parameters:

estricto - Switch indicando si queremos ser o no estrictos exigiendo que el automata este completamente especificado

Returns:

true/false segun el automata sea o no un AFD

es_AFD

public boolean es_AFD()

Determina si se trata de un Automata Finito Determinista (AFD). Es decir, lo aceptaremos si:
(1) para cada combinacion estado-terminal hay EXACTAMENTE 1 transicion (i.e. requiere que este completamente especificado)
(2) NO tiene E-transiciones

Returns:

true/false segun el automata sea o no un AFD (exigiendo que este completamente especificado)

es_AFD_no_especificado

public boolean es_AFD_no_especificado()

Determina si se trata de un Automata Finito Determinista (AFD) pero sin exigir que este completamente especificado. Es decir, lo aceptaremos si:
(1) para cada combinacion estado-terminal hay A LO SUMO 1 transicion (i.e. NO requiere que este completamente especificado)
(2) NO tiene E-transiciones

Returns:

true/false segun el automata sea o no un AFD (sin exigir que este completamente especificado)

determinizar

public AF determinizar()
                throws G_Exception,
                       AF_Exception

Devuelve al Automata Finito Determinista (AFD) equivalente a este automata. Si ya se trata de un AFD, devuelve una copia de si mismo.

Returns:

AFD equivalente

Throws:

G_Exception

AF_Exception

super_es_conexo

private boolean super_es_conexo(boolean store,
                                java.util.Collection acc,
                                java.util.Collection inacc)

Determina si se trata de un automata conexo o no, devolviendo ademas, si se desea, los conjuntos de estados accesibles e inaccesibles del automata.

Parameters:

store - Switch indicando s/n deseamos que devuelva los conjuntos de estados accesibles e inaccesibles

acc - Conjunto donde se almacenarian los estados accesibles AVISO: la variable debera estar inicializada

inacc - Conjunto donde se almacenarian los estados inaccesibles AVISO: la variable debe estar inicializada

Returns:

true/false segun el automata sea conexo o no

es_conexo

public boolean es_conexo()

Determina si se trata de un automata conexo o no.

Returns:

true/false segun el automata sea conexo o no

es_conexo

public boolean es_conexo(java.util.Collection acc,
                         java.util.Collection inacc)

Determina si se trata de un automata conexo o no, devolviendo ademas, los conjuntos de estados accesibles e inaccesibles del automata.

Parameters:

acc - Conjunto donde se almacenaran los estados accesibles AVISO: la variable debera estar inicializada

inacc - Conjunto donde se almacenaran los estados inaccesibles AVISO: la variable debe estar inicializada

Returns:

true/false segun el automata sea conexo o no

subautomata_conexo

public AF subautomata_conexo()
                      throws G_Exception,
                             AF_Exception

Devuelve al subautomata conexo equivalente a este automata. Si ya se trata de un automata conexo, devuelve una copia de si mismo.

Returns:

Subautomata conexo del automata

Throws:

G_Exception

AF_Exception

calc_size

private int calc_size(int n)

Calcula el tamanho necesario para el array que implementa la matriz de distinguibilidad del algoritmo de minimizacion

Parameters:

n - Numero de estados del automata a minimizar

Returns:

Tamanho del array auxiliar

get_xy

private int get_xy(int n,
                   int x,
                   int y)

Dada una posicion de la matriz de distinguibilidad del algoritmo de minimizacion, calcula el indice correspondiente en el array que lo implementa.

Parameters:

n - Numero de estados del automata

x - Coordenada x de la posicion de la matrix

y - Coordenada y de la posicion de la matrix

Returns:

Indice correspondiente en el array

init_distinguibles

private void init_distinguibles(int n,
                                boolean[] tabla,
                                java.util.Hashtable q2i,
                                Estado[] i2q,
                                AF afcnx)

Inicializa la matriz de distinguibilidad del algoritmo de minimizacion marcando (i.e. a true) las entradas correspondientes a pares (estado final, estado no final).

Parameters:

n - Numero de estados del automata

tabla - Array que implementa la matriz de distinguibilidad

q2i - Hash id. estado::indice en matriz

i2q - Hash (array) indice en matriz::id. estado

afcnx - Automata

print_distinguibles

private void print_distinguibles(int n,
                                 boolean[] matriz,
                                 java.util.Hashtable q2i,
                                 Estado[] i2q)

Imprime la matriz de distinguibilidad.

Parameters:

n - Numero de estados del automata

matriz - Array que implementa la matriz de distinguibilidad

q2i - Hash id. estado::indice en matriz

i2q - Hash (array) indice en matriz::id. estado

search_conj_qs

private int search_conj_qs(Estado q,
                           java.util.ArrayList a)

Busca el conjunto de estados equivalentes en el que esta almacenado un estado dado.

Parameters:

q - Estado a buscar

a - Lista de conjuntos de estados equivalentes en los que buscar

Returns:

Indice en el que se encuentra el conjunto de estados equivalentes que contiene el estado buscado; -1 si no lo encuentra

calc_distinguibles

private void calc_distinguibles(int n,
                                boolean[] tabla,
                                java.util.Hashtable q2i,
                                Estado[] i2q,
                                AF afcnx)

Obtiene la matriz de distinguibilidad del algoritmo de minimizacion marcando (i.e. a true) las entradas correspondientes a pares de estados equivalentes.

Parameters:

n - Numero de estados del automata

tabla - Array que implementa la matriz de distinguibilidad

q2i - Hash id. estado::indice en matriz

i2q - Hash (array) indice en matriz::id. estado

afcnx - Automata (conexo) a minimizar

get_equivalentes

private java.util.ArrayList get_equivalentes(int n,
                                             boolean[] tabla,
                                             java.util.Hashtable q2i,
                                             Estado[] i2q)

Devuelve los conjuntos de estados equivalentes (clases de equivalencia) en base a la matriz de distinguibilidad del algoritmo de minimizacion.

Parameters:

n - Numero de estados del automata

tabla - Array que implementa la matriz de distinguibilidad

q2i - Hash id. estado::indice en matriz

i2q - Hash (array) indice en matriz::id. estado

Returns:

Lista de conjuntos de estados equivalentes (i.e. clases de equivalencia)

calc_arcos_min

private java.util.LinkedHashSet calc_arcos_min(java.util.ArrayList conjs_qs,
                                               java.util.LinkedHashSet alfabeto_min,
                                               AF afcnx)

Obtener el conjunto de arcos/transiciones del automata minimo

Parameters:

conjs_qs - Lista de conjuntos de estados equivalentes (clases de equivalencia) del automata original

alfabeto_min - alfabeto del automata minimo

afcnx - Automata (conexo) a minimizar

Returns:

Conjunto de arcos/transiciones del automata minimo

generate_AFD_minimo

private AF generate_AFD_minimo(int n,
                               boolean[] tabla,
                               java.util.Hashtable q2i,
                               Estado[] i2q,
                               AF afcnx)

Construye el automata minimo resultante: ultima parte del proceso de minimizacion

Parameters:

n - Numero de estados del automata

tabla - Array que implementa la matriz de distinguibilidad

q2i - Hash id. estado::indice en matriz

i2q - Hash (array) indice en matriz::id. estado

afcnx - Automata (conexo) a minimizar

Returns:

Automata minimo resultante

minimizar

public AF minimizar()
             throws AF_Exception

Devuelve al Automata Minimo equivalente a este automata.

Returns:

Automata minimo equivalente

Throws:

AF_Exception - Si el automata no cumple las precondiciones: ser determinista completamente especificado