automatas finitas

AUTOMATA FINITO DETERMINISTA
Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y unconjunto de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada. El autómata finito acepta una cadena x si la secuencia de transiciones correspondientes a lossímbolos de x conduce desde el estado inicial a un estado final.
Si para todo estado del autómata existe como máximo una transición definida para cada símbolo del alfabeto, se dice que el autómata esdeterminantico (AFD). Si a partir de algún estado y para el mismo símbolo de entrada, se definen dos o más transiciones se dice que el autómata es no determinantico (AFND).
Un Autómata Finito Deterministaconsta de:
1. Un conjunto finito de estados, a menudo designado como Q.
de entrada y devuelve un estado. La función de transición se
designa habitualmente como ᵟ o Δ (delta).
2. Un conjunto finitode símbolos de entrada, a menudo designado como
∑ (sigma).
3. Una función de transición que toma como argumentos un estado y un
Símbolo
4. Un estado inicial, uno de los estados de Q.
5. Unconjunto de estados finales o de aceptación F. El conjunto F es un
Subconjunto de Q.

Formalmente un autómata finito se define como una 5-upla
M= (Q, Σ, q0, δ, F) donde:
* es un conjunto finito deestados;
* es un alfabeto finito;
* es el estado inicial;
* es una función de transición;
* es un conjunto de estados finales o de aceptación.

A menudo haremos referencia a un autómata finitodeterminista mediante su acrónimo: AFD. La representación más sucinta de un AFD consiste en un listado de los cinco componentes anteriores. Normalmente, en las demostraciones, definiremos un AFDutilizando la notación de«quíntupla» siguiente:
A= ( Q, ∑ , Δ ,q0, F )
Un autómata finito tiene como Funcionamiento
En el comienzo del proceso de reconocimiento de una cadena de entrada, el autómata...