CREACIÓN Y DEFINICIÓN DE UNA MAQUINA DE TURING (TEÓRICA Y PROGRAMACIÓN EN JAVA)

DESCRIPCIÓN DE LA MAQUINA DE TURING

La máquina de Turing, que se presenta a continuación, permite el ingreso de cadenas que empiecen con una cierta cantidad de 1’s, terminando la cadena con otra cierta cantidad de A’s, pero con la condición de que la cantidad de A’s ingresadas sea mayor a la cantidad de 1’s ingresadas. Como una manera de comprobación de esa condición, la maquina procesara la cadena y cambiara las primeras x cantidad de A’s por B’s, donde x seria la cantidad de 1’s ingresados.

Por ejemplo, para la entrada

“11AAAAA” devuelve en la cinta “11BBAAA”.

El autómata no acepta cadenas vacías.

´  Aprender a utilizar los autómatas finitos para modelar diferentes problemas

´ Adquirir las bases de teoría de autómatas y de lenguajes formales para aplicarla en futuros proyectos relacionados principalmente con compiladores inteligencia artificial robótica y control de procesos

DEFINICION DE LA MAQUINA DE TURING

MT=(conjunto de estados, alfabeto autómata, alfabeto de MT, estado inicial, símbolo de vacío, estado final, conjunto de transiciones).

MT=({q0,q1,q2,q3,q4},{1,A,B},{1,A,B,x,}, q0,,{q4},f),  donde...

f= { δ(q0,1)=(q1,x,R),

δ(q1,1)=(q1,1,R),

δ(q1,B)=(q1,B,R),

δ(q1,A)=(q2,B,L),

δ(q2,1)=(q2,1,L),

δ(q2,B)=(q2,B,L),

δ(q2,x)=(q0,1,R),

δ(q0,B)=(q3,B,R),

δ(q3,A)=(q3,A,R),

δ(q3,B)=(q3,B,R),

δ(q0,A)=(q5,A,R),

δ(q3,1)=(q5,1,R),

δ(q5,1)=(q5,1,R),

δ(q5,A)=(q5,A,R),

δ(q5,)=(q5,,R)

δ(q3,)=(q4,,S)

}

TABLA DE TRANSICIONES

GRAFOS

LENGUAJE ACEPTADO POR EL AUTÓMATA

CONJUNTO DE TRANSICIONES

CADENA PROBADA: 11AAAAA

 

GRAMATICA

G=({S},{1,A},P,S)

P= {

S→SA

S→1SA

S→1A }

CODIFICACIÓN EN JAVA

Para la codificación de esta maquina de Turing, utilizaremos el lenguaje de programación Orientado a Objetos JAVA, utilizando el entorno de desarrollo NETBEANS IDE.

Nos estaremos guiando de los grafos hechos en Jflap.

Para ello acá les dejo los tres vídeos donde explico la codificación paso a paso...

Vídeo 1: Parte introductoria, diseño de la Maquina.

Vídeo 2: Codificación

Vídeo 3: Codificación y parte final de la creación de la maquina.