Autonomas

OBJETIVO
Estudiar los autómatas finitos deterministas y los autómatas finitos no deterministas, los elementos que los forman así como la realización de sus diagramas y su funcionamiento.
JUSTIFICACIÓN
El estudio de los autómatas finitos deterministas es un tema importante para el análisis de cadenas, el analizar las cadenas implica mas de un estado y un análisis minuciosos de cada elemento dedeterminada cadenas.
INTRODUCCIÓN
En este tema analizaremos los dos tipos de autómatas deterministas y no deterministas, veremos cada uno de los elementos y restricciones de estos autómatas y en que consiste cada uno de ellos.
CONTENIDO
Esta maquina consiste en un dispositivo que puede estar en cualquiera de un numero finito de estados, uno de los cuales es el estado inicial y por lo menos unoes el estado de aceptación. A este dispositivo esta unido un flujo de entrada por medio del cual llega una secuencia de los símbolos de un alfabeto determinado. La maquina tiene la capacidad para detectar los símbolos conforme llegan y, basándose en el estado actual y el símbolo recibido, ejecutar una transición(de estado) que consiste en un cambio a otro estado o la permanencia en el estadoactual.
La determinación de cual será precisamente la transición que ocurra al recibir un símbolo depende del mecanismo de control de la maquina, programado para conocer cual debe ser el nuevo estado dependiendo de la combinación del estado actual y el símbolo de entrada. La palabra "finito" se refiere a que la maquina solo tiene un numero finito de estados. En ocasiones también se les menciona aestas maquinas como Autómatas Deterministas de Estados Finitos.
Formalmente un autómata finito determinista consiste en una quíntupla (S,,,i,F) donde:
* S: es un conjunto finito de estados.
* : es el alfabeto de la maquina.
* : es una función(función de transición) de SXS a S
* i: estado inicial(un elemento de S)
* F: conjunto de estados de aceptación (sub-conjunto de S)DIAGRAMA DE TRANSICIONES DETERMINISTA
Para representar un programa en el mecanismo de control utilizamos un diagrama de transiciones cuyos estados representan los estados de la maquina y cuyos arcos representan una posible transición de la maquina. Por lo tanto, los estados de inicio y aceptación del diagrama corresponden a los estados de inicio y aceptación del autómata.
Un diagrama para un AFDaceptara si y solo si su estado inicial es también un estado de aceptación.
El requisito del determinismo impone ciertas restricciones sobre los diagramas de transiciones que pueden aparecer en los programas para un autómata finito determinista. Se dice que un diagrama de transiciones es determinista si cumple las siguientes condiciones:

* En particular, cada estado de estos diagramas solo debetener un arco que sale para cada símbolo del alfabeto; de lo contrario, una maquina que llega a este estado se enfrentara a una elección de cual debe ser el arco a seguir.
* Además, dicho diagrama debe estar completamente definido, es decir debe existir por lo menos un arco para cada símbolo del alfabeto; de lo contrario, una maquina que llega a este estado puede enfrentarse a una situacióndonde no pueda aplicarse ninguna transición.
Ejemplo 1:
El siguiente diagrama no es determinista ya que no esta completamente definido; no representa cual será la acción que debe ocurrir sise recibe una letra o un dígito mientras se encuentra en el estado 2.

Ejemplo 2:
El siguiente diagrama tiene problemas similares ya que entre otras cosas no describe que deberá suceder si recibe un puntomientras se encuentra en el estado inicial.

No obstante, los dos diagramas vistos anteriormente no tienen mas de un arco de salida de un estado para cada símbolo y, por consiguiente, pueden modificarse para ajustarse a los requisitos del determinismo, aplicando lo siguiente:
* Añadimos un estado que representara un papel de captación global
* Para cada símbolo del alfabeto, dibujar un...