Automatas Finitos

Definición de autómatas finitos:

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 un conjunto 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 los sí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 es determinístico (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 determinístico (AFND). Formalmente un autómata finito se define como una 5-upla: M = <E, A, δ, e0, F>

Donde:

E: conjunto finito de estados

A: alfabeto o conjunto finito de símbolos de entrada

δ: función de transición de estados, que se define como

- δ: E x A → E si el autómata es determinístico

- δ: E x A → P(E) si el autómata es no determinístico (P(E) es el conjunto potencia de E, es decir el conjunto de todos los subconjuntos de E)

e0: estado inicial; e0 ∈ E

F: conjunto de estados finales o estados de aceptación; F ⊆ E.

...