Sistema De Construccion De Un Automata Finito Dada Una Gramatica

SISTEMA DE CONTRUCCION DE UN AUTOMATA FINITO DADA UNA GRAMATICA

Los procesos de conversión de una gramática a un autómata finito siempre se han llevado de una forma abstracta, en donde se toma la gramática y se convierte al AF todo esto realizado atravez de muchos pasos; esta nueva herramienta utiliza un método orientado a la Programación Orientada a Objetos usando VB.Net; capaz de reconoceruna gramática y arrojarnos su correspondiente AF.

2011

Universidad Simón Bolívar
24/06/2011

SISTEMA DE CONTRUCCION DE UN AUTOMATA FINITO DADA UNA GRAMATICA

SYSTEM OF CONSTRUCTIVE OF A GIVEN FINITE ROBOT A GRAMATY
Juan Carlos Yepes, Cesar Julio, Pablo Gelves,
Jeymer Vargas y Luis Puertas

RESUMEN

E
n este documento se describen las características de un software diseñado enVB.Net para la conversión de una gramática a un autómata finito o máquina de estado finito el cual es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y lo transforma en un autómata.

I. INTRODUCCION

El autómata es la primera máquina con lenguaje, es decir, un calculador lógico cuyo juego de instrucciones se orienta hacia los sistemas deevolución secuencial. [1]
En la historia nos podemos remontar en el año 1930, donde A. Turing desarrolló una máquina abstracta denominada Máquina de Turing para el estudio de la computación.
Luego en 1940´s y 1950´s, se desarrollan unas máquinas simples, en cuanto su funcionamiento, que fueron conocidas como autómatas finitos, para modelar el funcionamiento del cerebro.

También en los 1950´s, N.Chomsky comienza el estudio formal de las gramáticas (generadoras de lenguajes).
En 1969, S. Cook extiende el estudio de Tuning. Cook separa aquellos problemas que pueden ser solucionados de aquellos que en principio pueden ser solucionados pero que en la práctica toman demasiados recursos.

Actualmente Autómatas finitos y ciertas clases de gramáticas formales son usadas en el diseño yconstrucción de software. [14, 16]

II. MARCO TEORICO

II.I AUTÓMATA FINITO
Es un modelo matemático, que tiene un conjunto finito de estados; cada estado tiene la información para que una entrada dada pueda pasar a otra entrada. [1, 3, 15]
Además tiene un estado inicial y puede tener uno o varios finales o de aceptación (Ver fig. 1.0)

Formalmente, un autómata finito (AF) puede ser descrito comouna 5-tupla {,S,S0,F,δ} donde:
Es un alfabeto
S Un conjunto de estados
S0 Estado de inicio del AFD {qoЄ Q}
F Conjunto de estados de aceptación o reconocimiento de AFD F Q
δ Función de transición
QX⟾Q
También puede ser descrito por una grafica (Ver fig. 2.0) o por una tabla de transición (Ver fig. 3.0)

Los autómatas pueden reconocer cadenas de letras o números; carácter por carácter;para recorrer los autómatas se usan los métodos: [1, 15]
* 3
* 3’
El primero de ellos (3) utiliza como base una pila; es decir el ultimo en entrar es el primero en salir; todo eso se hace para saber si la cadena es reconocida o no; se dice que la cadena no es reconocida cuando el ultimo estado que dio como resultado es igual a vacio (); para saber si la cadena es reconocida o no hay quellegar hasta el ultimo carácter que se presenta en la cadena.
Por ejemplo usemos la cadena w = ababaaab; en la fig.4.0

Primero saquemos las partes que conforman este autómata; démosle un nombre un autómata llamémoslo H.
=a,b
S={q0,q1,q2}
S0={q0}
F={q1,q2}
La tabla de transición es:
δ | a | b |
→q0 | q1 | q0 |
F q1 | q2 | q2 |
F q2 | q2 | q2 |
Ahora utilicemos el método 3 parareconocer la cadena el cual se emplea de la siguiente forma: [4. 5, 15]
Tomemos la cadena w = abaaab
El método 3 nos dice que si
1. δq,αx=δδq,α,x
2. δq,α= δ(q, α)

1. δq0,w=δ (q0,abaaab)
En el primer paso el autómata recibe la cadena

2. δq0,abaaab=δ (δq0,a,baab)
En el segundo paso se analiza el primer carácter o letra con el estado de inicio y la otra parte queda en espera (q0,...