Definición De Los Autómatas Finitos Deterministas

Definición de los autómatas finitos deterministas

Temas por aprender
* Autómatas finitos
* Diagrama de estado de transición
* Estado de la tabla de transición
Contenido
Aquí vamos a definir formalmente los autómatas finitos, en autómatas finitos deterministas en particular y ver algunos ejemplos. Autómatas finitos reconocen los lenguajes regulares y, por el contrario, cualquieridioma, que es reconocido por un autómata finito es regular. Existen otros tipos de autómatas finitos como los autómatas finitos no deterministas y autómatas no deterministas con  y que van a ser estudiados más adelante. 

Vamos ahora a definir formalmente autómata finito determinista. 

Definición de autómata finito determinista 

Sea Q un conjunto finito y deje  un conjunto finito desímbolos. También permiten  una función de Q  a Q, vamos q 0 es un estado de Q y A un subconjunto de Q. Llamamos a los elementos de Q un estado ,  la función de transición , q 0, el estado inicial y un conjunto de estados de aceptación . 
A continuación, un autómata finito determinista es una 5-tupla <Q,  , Q 0,  , A> 

Notas sobre la definición 
1. El conjunto Q en la definición anterior essimplemente un conjunto con un número finito de elementos. Sus elementos pueden, sin embargo, interpretarse como un estado que el sistema (autómata) es in Así, en el ejemplo de la máquina expendedora, por ejemplo, los estados de la máquina, tales como "en espera de un cliente para poner una moneda en", "Han sido cinco centavos", etc, son los elementos de Q. "Esperando a un cliente para poner unamoneda en el" puede ser considerado el estado inicial del autómata y el estado en que la máquina da una lata de refresco se puede considerar el aceptación del Estado. 
2. La función de transición también se llama un estado de la función al lado lo que significa que el autómata pasa al estado  (Q, a) si cuenta con el símbolo de la entrada de un tiempo en el estado q. 
Así, en el ejemplo demáquinas expendedoras, si q es el estado inicial y una de cinco se pone en, a continuación,  (Q, a) es igual a "haber recibido cinco centavos". 
3. Tenga en cuenta que  es una función. Así, por cada estado q de Q y para cada uno de los símbolos  ,  (Q, a) debe ser especificado. 
4. Los estados de aceptación se utilizan para distinguir las secuencias de entradas dadas al autómata finito. Si elautómata finito se encuentra en un estado de aceptación cuando la entrada deja de venir, la secuencia de símbolos de entrada dado que el autómata finito es "aceptado". De lo contrario, no se acepta. Por ejemplo, en el ejemplo 1, la cadena de uno es aceptado por el autómata finito. Sin embargo, otras cadenas de texto como AA, AAA, etc no son aceptados. 
5. Un autómata finito determinista estambién llamado simplemente "un autómata finito". Abreviaturas como FA y DFA se utilizan para denotar autómata finito determinista.

DFA son a menudo representados por dígrafos llamada (estado) diagrama de transición . Los vértices (indicado por los círculos individuales) de un diagrama de transición de representar los estados de la DFA y los arcos marcados con un símbolo de entrada corresponden alas transiciones. Un arco (p, q) p desde el vértice a vértice q con la etiqueta  representa la transición  (P,  ) = Q. Los estados de aceptación se indican con círculos dobles. 
Funciones de transición también puede ser representado por las tablas como se muestra abajo. Se les llama tabla de transición . 

Ejemplos de lo finito autómata 

Ejemplo 1: Q = {0, 1, 2},  = {A}, A = {1}, el estadoinicial es 0 y  es como se muestra en la siguiente tabla. 
Estado (q) | De entrada (a) | Estado siguiente (  (Q, a)) |
0 | un | 1 |
1 | un | 2 |
2 | un | 2 |

Un diagrama de transición de estado para este DFA se presenta a continuación. 

Si el alfabeto  del Ejemplo 1 se cambia a {a, b} en lugar de {a}, entonces tenemos un ejemplo DFA como se muestra en la siguiente examle a aceptar...