versión PDF
Contents
1. XXOYa 1J01 XxOYOq 1 1 XxO0YOYq 2 XxOYOq 2 Y XXOYq 2 0Y XX0q 2 Y0Y XXq O OYOY XXXq 1 YOY XXXYq L OY XXXYOQ LIY XXXYOYaq 1 CADENA NO ACEPTADA Figure 6 Cadena de ejemplo 000101 la cual no es reconocida por el alfabeto2. qa Y R a q 0 R qa Y L q Y R 92 0 L 90 X R q2 Y L a sl q3 Y R qa B R 22333 Figure 1 Tabla de transiciones t 2 3 Programa 2 3 1 Descripci n Se codific un programa en Java que despliega las Descripciones Instant neas de la MT y determina si la cadena de entrada est en el alfabeto 01 El programa Java est compuesto por las siguientes funciones 2 3 2 Funciones codificadas e main Funci n principal del programa El programa cuenta con una interfaz visual compuesta de una ventana Frame de Java e turing_machine Esta funci n contiene el algoritmo encargado de recorrer y leer la cadena de entrada Recibe como par metro de entrada la cadena a analizar Mediante un ciclo while toma el estado actual y el s mbolo del cabezal en cada estado e invoca a la funci n determine action que contiene las reglas de la tabla de transiciones para determinar el siguiente estado movimiento de la cinta e determine action Esta funci n contiene la l gica de reglas de la tabla de transiciones de la figura 3 Recibe como par metros los siguientes valores 1 Estado actual Compuesto por una cadena num rica 0 1 2 3 4 2 S mbolo que lee el cabezal de la MT 0 1 X Y B donde X es una variable auxiliar para sustituir por ceros Y es usada para sustituir por unos y B representa el espacio en blanco as como tambi n t rmino de la cadena Con los val
3. construida en Mac OSX usando Netbeans La forma m s f cil para ejecutarla es mediante una l nea de comandos invocando al ejecutable como se describe en la siguiente secci n Adicionalmente si se requiere revisar el c digo fuente y recompilar se puede abrir el proyecto en el IDE Netbeans Requisitos 1 Cualquier Sistema Operativo con la Java Virtual Machine instalada 3 2 Ejecuci n del programa Pasos para ejecuci n 1 Descomprimir el tarball de archivos en la carpeta deseada de su equipo 2 Abrir una l nea de comandos e ir a la carpeta del paso 1 3 Escribir lo siguiente en la l nea de comandos y presionar enter java jar MT_alfabeto dist MT_alfabeto jar la im gen 2 muestra la l nea de comandos en y 1 programs java 77x12 e java bash Yanis MacBook Air 1 programs yani java jar MT_alfabeto dist MT_alfabeto jar Figure 2 Ejecuci n de la aplicaci n en l nea de comandos lo anterior ejecutar la ventana principal de la aplicaci n la cual se muestra en la figura 3 Complejidad Computacional Programa 11 Maquina de Turing de palabras 0An 1An Cadena ej 01 0011 000111 Reconocer Resultado Descripciones instant neas de la MT Notaciones afi n de estado de la MT Casilla le da es la casilla ad yacente a la derecha de gli PP Figure 3 Programa en ejecuci n 3 3 Uso del programa En la figura 3 se muestra el programa en eje
4. satisfy if state equals 1 amp amp symbol outputActions 0J 1 outputActions 1 0 outputActions 2 R return 1 Symbol satisfy if state equals 1 e symbol outputActions 0 2 outputActions 1 Y outputActions 2 L return 1 Symbol satisfy if state equals 1 amp amp symbol outputActions 0 1 outputActions 1 Y outputActions 2 R return 1 Symbol satisfy if state equals 2 amp amp symbol outputActions 0 2 outputActions 1 0 outputActions 2 L return 1 Symbol satisfy if state equals 2 amp amp symbol outputActions 0 0 outputActions 1 X outputActions 2 R return 1 Symbol satisfy if state equals 2 amp amp symbol outputActions 0 2 outputActions 1 Y outputActions 2 L return 1 Symbol satisfy if state equals 3 amp amp symbol outputActions 0 3 outputActions 1 Y outputActions 2 R return 1 Symbol satisfy if state equals 3 amp amp symbol outputActions 0 4 outputActions 1 B outputActions 2 R the alfabet equals 0 the alfabet equals 1 the alfabet equals Y the alfabet equals 0 4 the alfabet equals X 4 the alfabet equals Y 4 the alfabet equals Y 4 the alfabet equals B 61 62 10 11 12 13 14 16 17 1
5. 8 19 20 21 22 23 24 26 27 28 29 30 31 32 33 34 36 37 38 39 40 41 42 43 44 return 1 Symbol satisfy the alfabet Listing 2 Funci n turing_machine private void turing_machine String word Balada declaracion de variables de interfaz grafica Boal while state 4 if this determine_action state symbol outputActions 0 4 break state outputActions 0 char_symbol outputActions 1 Replace the variable replaced new StringBuilder word replaced setCharAt i char_symbol charAt 0 word replaced toString Add state number for strings of text area only replaced2 replaced replaced2 insert i 1 q statet word2 replaced2 toString if CoutputActions 2 equals R Move to Right IEH else Move to Left di this jtxtOutput append n this jtxtOutput append word2 Validates for final state if state equals 4 this jlblResultado setText CADENA ACEPTADA this jtxtOutput append n this jtxtQOutput append CADENA ACEPTADA if i lt word length symbol word substring i i 1 if symbol equals symbol B 46 47 48 49 50 if state 4 amp amp i lt word length state 0 3 Manual de Usuario 3 1 Requisitos para ejecuci n El programa es una aplicaci n Java sencilla con interfaz gr fica usando un Java jFrame Fue
6. Complejidad Computacional M quina de turing sobre alfabeto b 0 1 Yani www yaniweb com 8 de febrero de 2014 Resumen Construcci n e implementaci n de m quina de turing sobre el alfabeto b 0 1 correspondiente a la asignatura de Complejidad Computacional Se presenta en este documento el enfoque de soluci n y manual de usuario El documento tambi n est en version PDF Contents 1 Problema 1 2 Dl SOTO ee aa 4 Gok oe ee ee Se ee A a a A 2 2 2 Especificaci n formal 2 2 ee 2 2 3 Programaj ss cn ke eG ee e Oa eh a a a dd An 3 2 3 1 Descripci n coco somera a ead 3 2 3 2 Funciones Codificadas e 3 3 Manual de Usuario 6 3 1 Requisitos para ejecuci n ee 6 j i n del programa idos s a acii eie a aa aa a a a eek e i oboa d 6 3 3 Usoxdel prostamalls s lt o a ao a Po we a a ee Se me EO e E 7 3 4 Ejemplos Ejecutados 2 0 ee 7 3 4 1 Cadena QOOll 02 2 ee 7 3 4 2 Cadena QQQLL 2 2 a aae a a a a ee 8 34 3 Cadena OQ0LOU si o poyo SR goa ica e Re e a e e 9 1 Problema Dise e una m quina de Turing sobre el alfabeto b 0 1 b es el s mbolo blanco y a ada si fuera necesario s mbolos auxiliares que reconozca al lenguaje consistente de las palabras 0 1 con n E N Escriba un programa que reciba n y despliegue la manera en la que trabaja la m quina de Turing dise ada 2 Soluci n Se desarroll un programa que recibe como entrada la ca
7. cuci n Para ingresar cadenas se utiliza el cuadro de texto a un lado del bot n Reconocer Una vez ingresada se da clic en reconocer lo cual hace que se desplieguen los movimientos de la MT descripciones instant neas en la rea de texto as como el resultado final de la evaluaci n Cadena aceptada no aceptada Los estados se representan en la notaci n instant nea por q i y el s mbolo que se est leyendo en el cabezal es el adyacente a la derecha de q i 3 4 Ejemplos Ejecutados 3 4 1 Cadena 0011 La figura 4 muestra el comportamiento de la MT para la cadena 0011 la cual es una cadena correcta en el lenguaje del problema Figure 4 Cadena de ejemplo 0011 3 4 2 Cadena 000111 La figura 5 muestra el comportamiento de la MT para la cadena 000111 la cual es una cadena correcta en el lenguaje del problema Figure 5 Cadena de ejemplo 000111 3 4 3 Cadena 000101 La figura 6 muestra el comportamiento de la MT para la cadena 000101 la cual no es una cadena correcta en el lenguaje del problema Complejidad Computacional Programa 11 Maquina de Turing de palabras 04n 14n Cadena ej 01 0011 000111 000101 Resultado CADENA NO ACEPTADA Descripciones instant neas de la MT 000101 q 0 000101 Xq 1 00101 X0q 1 0101 X00q 1 101 X00Yq 2 01 3 X00q 2 Y01 Notaciones X0q 2 0Y01 qli n de estado de la MT A ELOYOL Casilla le da es la casilla ad Xx0q 1 Y01 yacente a la derecha de qfi
8. dena en el alfabeto 0 1 por ejemplo admite los siguientes valores 0011 000111 01 00001111 La idea principal del programa es cambiar primero un 0 por X y luego un 1 por una Y y as sucesivamente hasta que se hayan cambiado todos los ceros y unos 2 1 Algoritmo Algorithm 1 Algoritmo de funcionamiento de la MT para leer el alfabeto 071 Comenzar en extremo izquierdo de la entrada y cambiar el primer 0 por una X 0 X Mover hacia Izquierda pasando encima de todos los ceros y letras Y hasta encontrar un 1 1 Y Mover hacia Izquierda pasando encima de letras Y y ceros hasta encontrar una letra X Al encontrar la letra X busca un cero inmediatamente a la derecha y si lo encuentra lo cambia por una X y repite el proceso cambiando el 1 por una Y 6 Cuando la entrada no es de la forma 0 1 la MT no hace el siguiente movimiento y se para sin aceptar En caso contrario cuando cambia todos los ceros por X en la misma iteraci n en que los cambia el ltimo 1 por una Y entonces determina que la entrada es de la forma 0 1 y acepta la cadena 2 2 Especificaci n formal Se dise una m quina de Turing compuesta de un estado inicial qo tres estados posibles y un estado terminal q4 La especificaci n formal de la M quina de Turing dise ada para este problema es M do 41 42 93 qa 0 1 t do q4 La tabla de transiciones t para esta MT se especifica en la figura 3 Symbol State 0 1 X Y B q X R
9. ores anteriores se consulta en las reglas el estado siguiente el caracter que debe ser sustituido 0 1 X Y B y el movimiento siguiente Izquierda o Derecha I R los cuales son regresados en un arreglo de 3 elementos donde el elemento de la posici n 0 es el estado siguiente el de la posici n 1 el caracter a sustituir y en la posici n 2 el movimiento siguiente En el c digo fuente entregado con este documento se encuentra el proyecto MT_alfabeto proyecto de tipo Java en el cual se define el paquete mx cinvestav complexity MTalfabeto el cual contiene al archivo MT window java dentro del cual se pueden encontrar las funciones descritas anteriormente Los c digos de estas funciones se presentan a continuaci n Listing 1 Funci n determine action que representa a la tabla de transiciones t private int determine_action String state String symbol String outputActions if state equals 0 amp amp symbol equals 0 outputActions 0 1 outputActions 1 X outputActions 2 R return 1 Symbol satisfy the alfabet if state equals 0 amp amp symbol equals Y outputActions 0 3 11 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28 29 30 31 32 33 34 36 37 38 39 40 41 42 43 44 46 47 48 49 50 51 52 53 54 56 57 58 59 60 outputActions 1 Y outputActions 2 R return 1 Symbol
Download Pdf Manuals
Related Search