AUTÓMATA FINITO DETERMINISTA
Que tal a todos a partir de ahora andaré compartiendo el código fuente de algunos programas que hice en la Universidad, esperando que les sea de ayuda, tratare de poner comentarios dentro del código tratando de explicar de que sirve cada parte de este programa, también pueden publicar sus dudas y con mucho gusto tratare de responder a todas, sin mas por el momento continuemos.
El siguiente código se trata de un programa en java el cual funciona de Autómata Finito Determinista, siendo este realmente un autómata muy sencillo pero que espero les sirva de ejemplo pero primero explicare de que se trata un Autómata Finito Determinista.
Marco teórico:
El
autómata finito es un modelo matemático de un sistema con entradas y salidas
discretas. La tarea de un autómata finito es la de aceptar o rechazar una
cadena, determinando de esta manera si pertenece a un lenguaje dado o no.
Un
autómata finito determinista (AFD) se deferencia de los otros por lo siguiente,
para cada estado en que se encuentre el autómata, y cualquier símbolo del
alfabeto leído, existe siempre a lo más una transición posible desde ese estado
y con ese símbolo.
Definición
formal:
Un
autómata finito determinista es una 5-tupla (Q, Σ, q0,
δ, F), en donde:
- ( Q ) conjunto finito de estados
- (Q0) estado inicial
- ( Σ ) alfabeto
- δ Función de transición
- F conjunto de estados finales de aceptación
Algoritmo:
El siguiente Autómata finito determinista es capaz de
reconocer cadenas que cumplan con el siguiente criterio:
{an
bm | n >= 0, m>0}
Definición:
AFD
= ({q0, q1}, {a,b}, q0, δ, q1)
Tabla
de transición:
δ
|
a
|
b
|
q0
|
q0
|
q1
|
q1
|
q0
|
q1
|
Código fuente:
//Autómata Finito Determinista
//Materia Lenguajes y Autómatas I
//Autor:
//Ramos Salinas Arturo "DarkArtist"
//Visita mi Blog: codigodarkartist.blogspot.com
import javax.swing.*;
public class AFD
{
public static void main(String[] args)
{
int j=1;
while(j <= 5)//El Programa se repite 5 veces
{
char cadena [] = new char[4];//Arreglo para ingresar la cadena se puede cambiar de valor
int q=0;//iniciamos en el estado q0
JOptionPane.showMessageDialog(null,"El siguiente AFD es capaz de reconocer cadenas con la siguiente caracteristicas: \n\n a^n b^m donde m > 0");
for(int i=0; i<cadena.length; i++)
{//ciclo para ingresar valores
String entrada = JOptionPane.showInputDialog("Ingrese los caracteres del alfabeto:");
cadena[i]=entrada.charAt(0);//con charAt(0) obligo a la entrada de datos que solo tome el valor del primer dato que se ingreso
}
for(int i=0; i<cadena.length; i++)
{//ciclo para validar la cadena
if(q==0) //estado q0
{
if(cadena[i]=='a')
{
q=0; //se queda en q0
}
if(cadena[i]=='b')
{
q=1; //se va a q1
}
continue;
}
if(q==1) //estado q1
{
if(cadena[i]=='a')
{
q=0; //se regresa a q0
}
if(cadena[i]=='b')
{
q=1; //se queda en q1
}
continue;
}
}
if(q==1)
{
//si se queda en q1
JOptionPane.showMessageDialog(null,"La cadena es valida. ");
}
else
{
//de lo contrario
JOptionPane.showMessageDialog(null,"La cadena no es valida ");
}
j++;
}//Fin del While
}//Fin del main
}//Fin del Programa
Descargar AFD
//Autómata Finito Determinista
//Materia Lenguajes y Autómatas I
//Autor:
//Ramos Salinas Arturo "DarkArtist"
//Visita mi Blog: codigodarkartist.blogspot.com
import javax.swing.*;
public class AFD
{
public static void main(String[] args)
{
int j=1;
while(j <= 5)//El Programa se repite 5 veces
{
char cadena [] = new char[4];//Arreglo para ingresar la cadena se puede cambiar de valor
int q=0;//iniciamos en el estado q0
JOptionPane.showMessageDialog(null,"El siguiente AFD es capaz de reconocer cadenas con la siguiente caracteristicas: \n\n a^n b^m donde m > 0");
for(int i=0; i<cadena.length; i++)
{//ciclo para ingresar valores
String entrada = JOptionPane.showInputDialog("Ingrese los caracteres del alfabeto:");
cadena[i]=entrada.charAt(0);//con charAt(0) obligo a la entrada de datos que solo tome el valor del primer dato que se ingreso
}
for(int i=0; i<cadena.length; i++)
{//ciclo para validar la cadena
if(q==0) //estado q0
{
if(cadena[i]=='a')
{
q=0; //se queda en q0
}
if(cadena[i]=='b')
{
q=1; //se va a q1
}
continue;
}
if(q==1) //estado q1
{
if(cadena[i]=='a')
{
q=0; //se regresa a q0
}
if(cadena[i]=='b')
{
q=1; //se queda en q1
}
continue;
}
}
if(q==1)
{
//si se queda en q1
JOptionPane.showMessageDialog(null,"La cadena es valida. ");
}
else
{
//de lo contrario
JOptionPane.showMessageDialog(null,"La cadena no es valida ");
}
j++;
}//Fin del While
}//Fin del main
}//Fin del Programa
Descargar AFD