sintaxis maquinas de turing





UNIVERSIDAD TECNOLOGICA NACIONAL
FACULTAD REGIONAL CORDOBA.











SINTAXIS Y SEMANTICA DE LOS LENGUAJES

Trabajo Práctico de Laboratorio.

Curso: 2K2.










Tema: Simuladores de Autómatas


Alumno: Gaudenzi, María Pía Legajo: 67165
Cabrera, Gastón Legajo: 67051


Fecha de Entrega: 19/06/2012








INDICE





………………………………………………………………………………………pag 1
.-m,-








































OBJETIVO

A través del presente trabajo integrador de laboratorio se plantea el objetivo de observar cuales son los resultados que se obtienen al someter a distintos ejemplos de Autómatas con Pila y Maquinas de Turing a ser operadas por un simulador de autómatas y, de esta manera, poder observar su comportamiento en diferentes condiciones.
Semuestra además, cuáles fueron los criterios de selección del simulador escogido para simular los ejemplos pedidos y las características del mismo.



DESARROLLO

a) Los dos simuladores, tanto de Maquina de Turing como de Autómata con Pila, encontrados en la web son:
- JFLAP
- JFAST

A continuación, se comparan ambos simuladores teniendo en cuentalos requerimientos funcionales, requerimientos no funcionales y la interfaz.

1) Requerimientos Funcionales:

1.a) Definir los dominios de operación, representados por el alfabeto de entrada, alfabeto de cinta, alfabeto de pila y alfabeto de estados, según sea el tipo de máquina.

1.b) Editar, almacenar y recuperar la función de transición, que será definida como una tabla.

1.c) Definir lascondiciones iniciales de operación, que incluyen la cadena de entrada, el estado inicial, los estados finales y las posiciones de cabezales de lectura / escritura en caso de que corresponden.

1.d) Verificar la consistencia entre los dominios de operación, la función de transición y las condiciones iniciales de operación.

1.e) Ejecutar, a partir de la configuración inicial, los movimientosnecesarios hasta alcanzar una configuración final, que podrá ser de aceptación o rechazo.

1.f) Admitir dos modos de operación: i) completa, que cumplirá todos los movimientos necesarios desde la configuración inicial a la final y ii) paso a paso, donde cada paso implica la ejecución de un solo movimiento y es activado mediante un solo movimiento.

1.g) Determinar métricas o indicadores de operación,complejidad y/o eficiencia con el fin de facilitar la evaluación del desempeño de las maquinas y las operaciones entre ella. Estos indicadores dependerán de la maquina simulada.

2) Requerimientos no funcionales:

2.a) Probabilidad: el programa debe operar en cualquier plataforma sin la necesidad de cargar librerías específicas o productos de terceros ajenos al sistema operativo. Es decir que elarchivo ejecutable debe incluir toda función o recurso especial necesario para su operación.

2.b) Facilidad de uso: la operación del SMA debe ser simple, amigable y natural, y en los casos de que sea necesario debe haber una ventana que despliegue la ayuda correspondiente.

2.c) Robustez: el SMA debe estar preparado para reconocer el ingreso de datos incorrectos, que dará lugar a las advertencias delcaso y la no autorización del inicio del proceso de simulación. Se debe asegurar de que estos errores no serán nuca causa de falla. También se debe detectar la eventualidad de la repetición de una misma configuración, que sería un indicador de haber encontrado en un lazo de ciclo infinito.

2.d) Eficiencia: se trata de un requerimiento esencial de los procesos de simulación que involucran cálculonumérico intensivo, que no es el caso de los SMA. Sin embargo, la eficiencia debe ser considerada en la simulación de autómatas no deterministas con elevado factor de ramificación de sus árboles de descripciones instantáneas. La eficiencia también abarca los dominios y las condiciones de operación.

3) Interfaz Grafica (GUI):

3.a) Facilidad para la edición de dominios, función de transición y...