Fundamentos de Autómatas Finitos y su Implementación Práctica con JFLAP

Fundamentos Teóricos de los Autómatas

Definición y Comportamiento Básico

Una máquina (o máquina abstracta) es un modelo digital y discreto utilizado en la ciencia de la computación. Para simplificar la comprensión, es útil comparar su comportamiento con el de una máquina expendedora.

El comportamiento básico de un autómata es siempre el mismo: la máquina recibe desde el exterior una secuencia de caracteres (comandos). La máquina se encuentra en un estado. Cada vez que llega un carácter de entrada, se ajusta un nuevo estado (el Estado Sucesor), dependiendo del carácter de entrada y del estado actual. Esto se conoce como Transición de Estado o simplemente Transición.

Usted puede especificar el conjunto de las transiciones de estado posibles, lo que define el comportamiento de la máquina cuando el programa comprende la máquina.

Elementos Clave del Autómata

Transiciones y Estados

• Transiciones: Las transiciones se describen mediante una función de transición. Una transición permite cambiar de un estado a otro particular. En cualquier momento, el autómata se encuentra exactamente en un estado (Q).
• Estado Inicial (Startzustand): Es el estado de comienzo. Se representa con una flecha.
• Estado Final (Endzustand): Se representa con un doble círculo. Una máquina puede tener varios estados finales.
• Comentario sobre Transiciones: La transición se inicia desde el estado actual y se etiqueta con la acción correspondiente.

Entrada y Alfabeto

• Entrada: Es la secuencia de acciones que recibe el autómata. El autómata considera las acciones individuales en secuencia y reacciona en consecuencia. (Puede ser una secuencia de números, palabras, caracteres o letras; en una máquina real, pueden ser botones, monedas o selecciones).
• Alfabeto de Entrada: Es el conjunto de caracteres, palabras o símbolos a los que el autómata puede responder.

Aceptación y Lenguaje

• Comportamiento de Aceptación: El autómata acepta la palabra de entrada si, y solo si, después de leer toda la palabra, se encuentra en un estado final. De lo contrario, no acepta la palabra (la rechaza).
• Palabra: Es una cadena compuesta por caracteres del alfabeto.
• Lenguaje de la Máquina: Es el conjunto de todas las palabras que el autómata acepta. Se dice que el autómata *reconoce* este lenguaje.

Concepto Adicional: Sistema Binario

Sistema Binario: 11011 = 1*(2^0) + 1*(2^1) + 0*(2^2) + 1*(2^3) + 1*(2^4) = 1 + 2 + 0 + 8 + 16.

Creación de Autómatas con JFLAP

A continuación, se detallan los pasos para la creación y modificación de autómatas utilizando la herramienta JFLAP:

1. Establecer Estados

   Selecciona el modo 'Estado' (State Mode). Ahora, usando el botón circular, puedes añadir tantos estados como desees haciendo clic con el ratón.

2. Establecer Transiciones y Acciones

   Selecciona el modo 'Transición' (Transition Mode). Conecta el estado de origen (haciendo clic en él) con el estado de destino (soltando el ratón sobre él). De esta manera, también puedes crear una transición de un estado a sí mismo.

3. Eliminar Estados/Transiciones

   Selecciona el modo 'Eliminar' (Delete Mode). Ahora, usando el botón del cráneo, puedes hacer clic en los estados o transiciones que deseas eliminar.

4. Modificar Estados

   Haz clic derecho sobre un estado para que se muestre un menú contextual. Por ejemplo, puedes seleccionar:

   • Final: Para establecerlo como estado final.
   • Inicial: Para establecerlo como estado inicial.

Puedes guardar el modelo usando la opción de menú Archivo > Guardar como....