Page 56 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 56
56
símbolos que le pertenecen.
3- Puede ser reconocido mediante un autómata finito, este puede saber si una cadena de
símbolos pertenece o no al lenguaje, que lee la máquina.
Un ejemplo de lenguaje regular el conjunto de todos los números pares enteros positivos.
¿Qué es un autómata?
La palabra autómata evoca algo que pretende imitar las funciones propias de los seres vivos,
especialmente relacionadas con el movimiento, en pocas palabras cuando pensamos en un
autómata, pensamos en un robot y si es antropomorfo, más se acerca a nuestra concepción, de
hecho, lo tenemos como una máquina que hace cosas que tendríamos que hacer nosotros.
Un ejemplo de una “maquina real” que automatiza un proceso puede ser una máquina empacadora
de algún producto que se fabrique en serie y con una serie de instrucciones, pasos y características
definidas e iguales para cada salida o producto final.
De hecho, este puede ser un autómata y puede ser también un hacedor de tareas que no tiene
necesariamente un cuerpo o hardware asociado a la tarea.
En el campo de los traductores, procesadores, compiladores e intérpretes, lofundamental no es la
simulación del movimiento, sino la simulación de procesos para tratar información. Este es el
enfoque dado a la temática de este curso.
Las maquinas se estudiarán como abstracciones matemáticas que capturan solamente el aspecto
referente a las secuencias de eventos que ocurren, sin tomar en cuenta ni la forma de la maquina
ni sus dimensiones (aspectos de hardware por referir una analogía); aunque trataremos también
de trabajar en esa dirección de creación de autómatas, con los trabajos que se han asignado.
La información se codifica en cadenas de símbolos, y un autómata es un dispositivo que manipula
cadenas de símbolos que se le presentan a su entrada, produciendo otras tiras o cadenas de
símbolos a su salida.
El autómata recibe los símbolos de entrada, uno detrás de otro, es decir secuencialmente. El
símbolo de salida que en un instante determinado produce un autómata, no sólo depende del
último símbolo recibido a la entrada, sino de toda la secuencia o cadena, que ha recibido hasta ese
instante.
Atendiendo al plan iniciamos con las maquinas abstractas más simples, los autómatas finitos, las
cuales están en relación con los lenguajes regulares.
Todo lo anterior conduce a definir un concepto fundamental: el estado de un autómata.
¿Qué trata la temática de “modelado de sistemas discretos”?
La noción más básica de los modelos de eventos discretos es la de estado. Un estado es una
situación en la que se permanece un cierto lapso.
Los estados se representan por óvalos, y los eventos por flechas entre los óvalos, llamadas
transiciones. Dentro de cada estado se escribe su nombre, mientras que al lado de las transiciones
se escribe el nombre del evento asociado. El estado inicial está siendo indicado por un triángulo
o flecha y un estado final o de aceptación, mediante doble círculo. Los estados finales indican que