Automatas

AUTOMATA FINITO DETERMINISTA

Un Autómata Finito Determinista consiste en un dispositivo que puede estar en cualquier estado entre un número finito, uno de los cuales es el estado inicial y por lo menos uno es un estado de aceptación.

A este dispositivo está unido un flujo de entrada por medio del cual llegan en secuencia los símbolos de un alfabeto determinado.

La máquina tiene capacidadpara detectar los símbolos conforme llegan y, basándose en el estado actual y el símbolo recibido, ejecutar una transición consistente en cambiar a otro estado o la permanencia en el mismo.

El programa de un Autómata Finito Determinista no debe contener ambigüedades (para un estado un determinado símbolo sólo puede producir una determinada acción).

Se dice que un Autómata FinitoDeterminista acepta su cadena de entrada si, después de comenzar sus cálculos en el estado inicial la máquina cambia a un estado de aceptación después de leer el último símbolo de la cadena.

Si después de leer el último símbolo no queda en estado de aceptación, se dice que la cadena ha sido rechazada. Si la entrada es una cadena vacía (l) será aceptada si y sólo si el estado inicial es también un estadode aceptación.

Un Autómata Finito Determinista consiste en una quíntupla ( S, S, d, i, F) donde:

• S, es un conjunto finito de estados. • S, es el alfabeto de la máquina. • d, es una función (función de transición) de S× S a S. • i, (un elemento de S) es el estado inicial. • F (un subconjunto de S) es el conjunto de estados de aceptación.

La interpretación de la función de transición d deun autómata finito determinista es que d(p,x)=q sí y sólo sí la máquina puede pasar de un estado p a un estado q al leer el símbolo x.

El diagrama de transición determinista sólo debe tener un arco que sale de un estado para cada símbolo del alfabeto. Además, dicho diagrama está completamente definido, es decir, debe existir un arco para cada símbolo del alfabeto.

Las características de losautómatas finitos determinísticos son:

1. Un conjunto finito de estados y un conjunto de transiciones de estado a estado, que se dan sobre símbolos de entrada tomados de un alfabeto S .

2. Para cada símbolo de entrada existe exactamente una transición a partir de cada estado (posiblemente de regreso al mismo estado).

3. Un estado, por lo general denotado como q0 es el estado inicial, enel que el autómata comienza.

4. Algunos estados (tal vez ninguno) están designados como final o de aceptación. Un autómata finito determinístico es una quinta tupla (Q, S , d , q0, F) donde:

Q es un conjunto finito de estados.

S un alfabeto de entrada finito.

q0 elemento de Q , el estado inicial.

FÍ Q el conjunto de estados finales o de aceptación.

d es la función d : Q x S ® Qque determina el único estado siguiente para el par (q1, s ) correspondiente al estado actual q1 y la entrada s . Generalmente el término autómata finito determinístico se abrevia como DFA de sus siglas en inglés Deterministic Finite Automaton. Usaremos M = (Q, S , q0, F, d ) para indicar el conjunto de estados, el alfabeto, el estado inicial, el conjunto de estados finales y la función asociadascon el DFA M.

Se puede construir un diagrama para que ayude a determinar los distintos miembros o cadenas del lenguaje. Tal diagrama tiene la forma de un grafo dirigido con información añadida, y se llama diagrama de transición. Los nodos del grafo corresponden a los estados del DFA y se usan para señalar, en ese momento, hasta qué lugar se analizó la cadena.

Por lo general q0 es el estadoinicial, marcando con una flecha (® ), el comienzo del autómata; algunos estados están designados como final o aceptación indicados por un doble círculo. Los símbolos del alfabeto son las etiquetas de los arcos del grafo. Si cuando ha sido tratada la cadena en su totalidad se termina en un estado de aceptación entonces la cadena es aceptada por el lenguaje. Si M es un AFD, entonces el lenguaje...