Los Autómatas Finitos Deterministicos (Parte III)

abdulmath (62)in #science • 8 years ago

Este post es tercera entrega de la seri de Los Autómatas Finitos Deterministicos I y II el cual es parte del curso de adiestramiento "Introducción a las Redes de Petri". Comenzemos...

Los autómatas vienen a ser mecanismos formales que "realizan" derivaciones en gramáticas formales. La manera en que las realizan es mediante la noción de reconocimiento. Una palabra será generada en una gramática si y sólo si la palabra hace transitar al autómata correspondiente a sus condiciones terminales.

Un autómata finito con alfabeto A es un multigrafo dirigido, en el cual cada arista está rotulada con una letra del alfabeto A. Los vértices se consideran como los estados internos en que puede estar el autómata. Una palabra se dice que es aceptada por el autómata si existe un camino dirigido que comienza en el estado inicial, se compone de arcos rotulados consecutivamente y termina en un estado final. El lenguaje aceptado por un autómata finito es el subconjunto de A* formado por todas las palabras aceptadas.

Estos son los autómatas finitos más sencillos. Se construyen a partir de un conjunto de estados Q y de un conjunto de símbolos de entrada T. Su funcionamiento queda determinado por una función de transición t:QxT----> Q.

En todo autómata finito se cuenta con un estado inicial, q0 de Q y un conjunto de estados finales F subconjunto de Q.

(Q,T,t,q0,F)

Ejemplo

El siguiente diagrama representa un autómata finito determinista con alfabeto A={a,b} y estados 0, 1 y 2. El estado inicial es el 0 y el 2 es el único estado final, indicado por el doble círculo.

Por ejemplo la palabra bab es aceptada, en cambio ba no es aceptada, pues luego de recorrer arcos rotulados b y a partiendo de 0, se termina en 1, que no es un estado final.