SSL: introducción al diseno de autómatas finitos 1

Como hemos visto, los LRs se representan, generalmente, por medio de ERs, aunque también pueden ser descriptos mediante frases en un Lenguaje Natural, o expresados a través de conjuntos por enumeración y por comprensión.

Independientemente de cómo se lo representa, ufn LR existe; y este lenguaje debe ser RECONOCIDO por algún objeto. Este objeto también existe y se lo denomina AUTÓMATA FINITO (AF).

5.1  ¿QUÉ ES UN AUTÓMATA FINITO?

Un Autómata Finito (AF) es una herramienta abstracta que se utiliza para reconocer un determinado LR. En otras palabras: un AF es un modelo matemático de un sistema que recibe una cadena constituída por caracteres de cierto alfabeto Σ y tiene la capacidad de determinar si esa cadena pertenece al LR que el AF reconoce.

** RECONOCER un LR significa aceptar cada cadena que es una palabra del LR y rechazar cada cadena que no pertenece al lenguaje.

Para realizar esta tarea de reconocimiento, el AF recorre, uno por uno, los caracteres que constituyen la cadena con la que ha sido “alimentado”. Cada carácter procesado produce un cambio de estado en el AF. Si al terminar de analizar todos los caracteres de la cadena, el AF se encuentra en un estado especial llamado ESTADO FINAL (EF) o Estado de Aceptación, entonces se afirma que el AF ha reconocido a la cadena y, por lo tanto, ésta es una palabra del lenguaje; caso contrario, la cadena es rechazada porque no pertenece al LR tratado. Un AF puede tener varios estados finales.

Existe otro estado especial en todo AF: el estado en el que se encuentra antes de comenzar su actividad. A este estado se lo denomina ESTADO INICIAL (EI) y tiene la característica de ser único, es decir: cada AF tiene un único estado inicial.

Todo AF tiene asociado un digrafo, llamado Diagrama de Transiciones (DT), que permite visualizar con mayor claridad el funcionamiento del AF. En este diagrama, los nodos del digrafo representan los diferentes estados del AF, y los arcos, que representan las transiciones entre los estados, informan cada cambio de estado que ocurre en el AF según el carácter que “leyó” de la cadena en estudio. Por ello, las transiciones estarán etiquetadas con símbolos del alfabeto.