Autómatas Ejercicios

AFN, AFD y Construcción de
Thompson
Utilizando JFLAP
Un autómata finito es un modelo matemático de una
máquina que acepta cadenas de un lenguaje
definido sobre un alfabeto A.
Profesor: EdgardoAdrián Franco Martínez
Materia: Teoría Computacional
Nombre: Mejía Placido Rosa Isela.
12/09/2011

Materia: Teoría Computacional
Profesor: Edgardo Adrián Franco Martínez
Nombre: Mejía PlacidoRosa Isela
Grupo: 2CV1

Autómata finito

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 conjuntofinito 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 transicionescorrespondientes a los símbolos de x conduce desde el estado inicial a un estado final.

Clasificación de los autómatas finitos
Cuando se definió autómata finito, la función, es en general nodeterminista. Así en función de f,
se hablará de autómatas finitos deterministas AFD y autómatas finitos no deterministas AFND.

Un autómata finito no determinista AFND se caracteriza por la posibilidadde que
dada una entrada e en un estado qi, se pueda pasar a un estado qj, qk,...,qn sin saber a
ciencia cierta, a cual de esos estados pasará. Existiendo la misma probabilidad de que
pase acualquiera de dichos estados.

Un autómata finito determinista AFD es un caso particular de los autómatas finitos,
en el que la función de transición no presenta ninguna ambigüedad en las transiciones
deestados para una entrada dada.

Autómatas finitos no deterministas (AFN)
La definición de autómata finito no determinista AFND o AFN coincide con la de
autómata finito:



Con la salvedad deque
es no determinista, i.e. es aquel que
presenta cero, una o más transiciones por el mismo carácter del alfabeto.



Un autómata finito no determinista también puede o no tener más de un...