Maquina De Turing En Java

En esta ocasión  les presentaré una simulación de la maquina de Turing que acepta cadenas del tipo anbn

Lo Primero que tenemos que hacer es crear una clase llamada Accion que tendrá como atributo siguiente_estado, nuevo_símbolo y movimiento  y su correspondiente constructor.

public class Accion {
 
    public String siguiente_estado;
    public String nuevo_simbolo;
    public String movimiento;

    public Accion(String siguiente_estado, String nuevo_simbolo, String movimiento) {
        this.siguiente_estado = siguiente_estado;
        this.nuevo_simbolo = nuevo_simbolo;
        this.movimiento = movimiento;
    }
}

Luego crearemos la clase Parser, en esta clase es donde recibiremos el archivo txt con la cadena de reglas.

public class Parser {
 
    private Scanner scanner;
    private HashMap transicion;

    public Parser(File file) {
        try {
            scanner = new Scanner(file);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
 
 
    public String getInput() {
        return scanner.nextLine();
    }

    public HashMap parse() {
        transicion = new HashMap();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            parseLine(line);
            System.out.println(line);
        }
        System.out.println("\n");
        return transicion;
    }

    public void parseLine(String linea) {
        linea = linea.replaceAll("\\s", "");
        int i = linea.indexOf("->");
        String keyState = linea.substring(0, i);
        keyState = keyState.replaceAll(",", "");
        linea = linea.substring(i + 2, linea.length());
        String[] array = linea.split(",");
        Accion action = new Accion(array[0], array[1], array[2]);
        transicion.put(keyState, action);
    }
}

Después crearemos las clase MaquinaTuring que es la que contendrá la lógica de esta simulación.

public class MaquinaTuring {
 
    private String estadoActual;
    private int cursor;
    private String entrada;
    private HashMap<String, Accion> transicion;
    public  ArrayList<String> cinta;
    private static String ESPACIO_BLANCO = "B";
    private boolean pasos = false;
    private String ESTADO_FINAL = "qf";

    public MaquinaTuring(String entrada, HashMap transicion, boolean pasos) {
        this.entrada = entrada;
        this.transicion = transicion;
        this.pasos = pasos;
        cinta = new ArrayList<String>();
        init();
    }

    private void init() {
        for (int i = 0; i < entrada.length(); i++) {
            cinta.add(String.valueOf(entrada.charAt(i)));
        }
        cinta.add(ESPACIO_BLANCO);
        cursor = 1;
        estadoActual = "q1";
    }

    public void run() {
        while (true) {
            display();
            if (cursor == 0) {
                paso_derecha();
                cursor = 1;
            }
            Accion action;
            String key = estadoActual + cinta.get(cursor);
            if ((action = transicion.get(key)) != null) {
                exec(action);
                if (estadoActual.equals(ESTADO_FINAL)) {
                    detener();
                    break;
                }
            } else {
                detener();
                break;
            }
            if (pasos) {
                System.out.println("Presione ENTER para continuar...");
                new Scanner(System.in).nextLine();
            }
        }
    }

    private void paso_derecha() {
        cinta.add("B");
        for (int i = cinta.size() - 1; i > 0; i--) {
            Collections.swap(cinta, i, i -1);
        }
    }

    public void exec(Accion accion) {
        cinta.set(cursor, accion.nuevo_simbolo);
        estadoActual = accion.siguiente_estado;

        cursor += accion.movimiento.equals("R") ? 1 : - 1;
    }


    public void detener() {
        if (estadoActual.equals(ESTADO_FINAL)) {
            System.out.println("Ok");
        } else {
            System.out.println("OK");
        }
    }

    public void display() {
        System.out.print(cinta);
        System.out.println(" | estado: " + estadoActual);
        for (int i = 0; i < cinta.size(); i++) {
            System.out.print(" ");
            if (i == cursor) {
                System.out.print("^");
                break;
            }
            System.out.print("  ");
        }
        System.out.println();
    }
}

Ahora crearemos la clase Main para poner en practica todo este codigo

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
     
        boolean pasos = false;
 
        if (args.length == 2) {
            if (args[1].equals("s")) {
                pasos = true;
            }
        }
     
        Parser parser = new Parser( new File("ruta del archivo"));
        String entrada = parser.getInput();
        HashMap transicion = parser.parse();

        new MaquinaTuring(entrada, transicion, pasos).run();
    }
 
}

Realizando un ejemplo con un archivo txt que podrán descargar AQUI , la salida sería la siguiente.

El proyecto lo podrán descargar AQUI

• Tweet
• Share
• Share
• Share
• Share