ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Package Algoritmos


Enviado por   •  27 de Junio de 2014  •  3.017 Palabras (13 Páginas)  •  259 Visitas

Página 1 de 13

package algoritmos;

import estructuras.*;

import analisis.Alfabeto;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

public class Subconjuntos {

/**

* Log para el algoritmo de subconjuntos.

*/

private static Log log = new Log();

/**

* Realiza la conversión de un AFN a un AFD, aplicando el

* algoritmo 3.20 del libro de Compiladores de Aho (2a. ed).

* @param afn El <code>AFN</code> a convertir.

* @return El <code>AFD</code> equivalente a <code>afn</code>.

*/

public static AFD getAFD(Automata afn) {

Estado estadoOrigen, estadoDestino;

// Logging

log.vaciar();

log.agregar("Cálculo de conjuntos de estados".toUpperCase()).nuevaLinea();

log.agregar("-------------------------------").nuevaLinea().nuevaLinea();

/* AFD resultante */

AFD afd = new AFD(afn.getAlfabeto(), afn.getExprReg());

/* Conjunto de estados finales del AFD */

Conjunto<Conjunto<Estado>> estadosD = new Conjunto<Conjunto<Estado>>();

/*

* En esta cola se iran almacenando temporalmente los conjuntos de

* estados y la operación de marcarlos consistirá en quitarlos la misma

* y guardarlos en estadosD.

* La condición de que no haya estados marcados se dará cuando la cola

* esté vacía.

*/

Queue<Conjunto<Estado>> colaTemp = new LinkedList<Conjunto<Estado>>();

/* Contador de estados procesados del AFD */

int estadosProcesados = 0;

/* Calculamos la Cerradura Epsilon del estado inicial */

Conjunto<Estado> resultado = cerraduraEpsilon(afn.getEstadoInicial());

// Logging

log.agregar("cerradura(" + afn.getEstadoInicial() + ") = " + resultado).nuevaLinea().nuevaLinea();

/*

* Agregamos la Cerradura Epsilon del estado

* inicial del AFN a estadosD sin marcar

*/

estadosD.agregar(resultado);

colaTemp.add(resultado);

/*

* Iniciamos el ciclo principal del algoritmo

*/

while (!colaTemp.isEmpty()) {

/* Marcar T */

Conjunto<Estado> T = colaTemp.remove();

/* Agregamos el correspondiente estado al AFD */

if (afd.cantidadEstados() < estadosD.cantidad())

afd.agregarEstado(new Estado(afd.cantidadEstados()));

/* Estado del AFD a procesar */

estadoOrigen = afd.getEstado(estadosProcesados++);

/* Buscar transiciones por cada simbolo */

for (String simbolo : afn.getAlfabeto()) {

/* Aplicar cerraduraEpsilon(mueve(T, simbolo)) */

Conjunto<Estado> M = mover(T, simbolo);

Conjunto<Estado> U = cerraduraEpsilon(M);

// Logging

log.agregar("cerradura(mover(" + T + ", " + simbolo + ")) = ")

.agregar("cerradura(" + M + ") = " + U)

.nuevaLinea();

if (estadosD.contiene(U)) {

int posicion = estadosD.obtenerPosicion(U);

estadoDestino = afd.getEstado(posicion);

}

else if (!U.estaVacio()) {

estadoDestino = new Estado(afd.cantidadEstados());

afd.agregarEstado(estadoDestino);

/* Agregar U a estadosD (sin marcar) si no está aún */

estadosD.agregar(U);

colaTemp.add(U);

}

else {

/*

* Encontramos un conjunto vacío, por tanto,

* no debemos agregar ninguna transición y

* debemos saltar directamente a evaluar el

* siguiente simbolo del alfabeto.

*/

continue;

}

// Agregamos la transición al AFD

Transicion trans = new Transicion(estadoDestino, simbolo);

estadoOrigen.getTransiciones().agregar(trans);

}

// Logging

log.nuevaLinea();

}

/* Establecemos los estados finales del AFD */

for (int i=0; i < estadosD.cantidad(); i++) {

Estado estadoAFD = afd.getEstado(i);

for (Estado e : estadosD.obtener(i)) {

if (e.getEsFinal()) {

estadoAFD.setEsFinal(true);

break;

}

}

}

afd.setEstadosD(estadosD);

return afd;

...

Descargar como (para miembros actualizados) txt (10 Kb)
Leer 12 páginas más »
Disponible sólo en Clubensayos.com