lunes, 16 de enero de 2017

Programando mi primer autómata en Java

Navegando en el foro de Java México me encontré con un post en el que solicitan ayuda para programar un autómata que reconozca el siguiente patrón 0*(11)+0* Me pareció interesante la nota, el Autómata debe aceptar cadenas con al menos un par de 1, rodeados de uno, muchos o ningún cero.

Cadenas aceptadas:
11
00000110000
11000
0000011
01111000

Cadenas no aceptadas:
001100110
0000111
111000
0101011
110011

Me he tomado el tiempo de hacer el diagrama del autómata

Aquí el código fuente

   

/*
 * Automata11
 * Copyright (C) 2017 Roberto Lopez marcos.robrto.lopez@gmail.com
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
package com.rlopez.demo.automata;

import javax.swing.JOptionPane;

/**
 *
 */
public class Automata11 {
 //init state

 private static final int Q0 = 0;
 private static final int Q1 = 1;
 private static final int Q2 = 2;
 private static final int Q3 = 3;
 private int state;
 public StringBuilder buffer;

 public Automata11() {
  state = Q0;
 }

 public int getState() {
  return state;
 }

 public boolean accept(String str, boolean debug) {
  init();
  for (char c : str.toCharArray()) {
   int previousState = state;
   appendChar(c);
   System.out.println("'" + c + "' " + getStateName(previousState) + " -> " + getStateName(state));
  }
  return state == Q3;
 }

 private void init() {
  state = Q0;
  buffer = new StringBuilder();
 }

 private String getStateName(int stateToGet) {
  String stateName = "";
  switch (stateToGet) {
   case Q0:
    stateName = "Q0";
    break;
   case Q1:
    stateName = "Q1";
    break;
   case Q2:
    stateName = "Q2";
    break;
   case Q3:
    stateName = "Q3";
    break;
  }
  return stateName;
 }

 private void appendChar(char character) {
  if (character != '1' && character != '0') {
   System.err.println("Invalid character");
   return;
  }
  buffer.append(character);
  switch (state) {
   case Q0:
    if (character == '1') {
     state = Q1;
    } else {
     state = Q0;
    }
    break;
   case Q1:
    if (character == '1') {
     state = Q3;
    } else {
     state = Q2;
    }
    break;
   case Q2:
    //not matter accept any character
    state = Q2;
    break;
   case Q3:
    if (character == '1') {
     state = Q1;
    } else {
     state = Q3;
    }
    break;
   default:
    System.err.println("Error unknow state");

  }
 }

 public static void main(String args[]) {
  String string = JOptionPane.showInputDialog(null, "Enter the string with 0 and/or 1");
  Automata11 automata11 = new Automata11();
  System.out.println("The enter String '" + string + " is accept?:" + automata11.accept(string, true));

 }
}


   
Salida:
   

'0' Q0 -> Q0
'0' Q0 -> Q0
'0' Q0 -> Q0
'1' Q0 -> Q1
'1' Q1 -> Q3
'1' Q3 -> Q1
'1' Q1 -> Q3
'0' Q3 -> Q3
'0' Q3 -> Q3
The enter String '000111100 is accept?:true

   

No hay comentarios:

Publicar un comentario

Hola A todos