Exposición Equipo 2_AFBD a AFD - Mauricio axel 20 (1)

Vista previa del material en texto

TECNOLOGICO NACIONAL DE MEXICO
instituto TECNOLOGICO DE ACAPULCO
Conversión de un autómata finito no determinado (afnd) a autómata finito determinado (afd)
EQUIPO 2.
Integrantes del equipo.
ABARCA LOPEZ ALBERTO JOSUE
LOPEZ ANSELMO MAURICIO AXEL 
CANTU PALACIOS CARLOS ALBERTO
RAMOS PEREZ INES GUADALUPE
CONVERSIÓN
Transformación de autómata finito no determinista a autómata finito determinista. Todo AFND estricto, o sea un AFND que no es AFND-V, puede ser transformado a AFD utilizando un algoritmo que transforma los estados del AFND en nuevos estados que son subconjuntos de los estados originales y aplica a los mismos la clausura para confirmar la conexidad entre cada uno de los componentes y así eliminar el indeterminismo.
Este algoritmo aunque siempre obtiene un AFD equivalente no puede decirse que sea la versión minimal del mismo, para ello deben aplicarse otras transformaciones.
CONVERSIÓN
Sea un autómata finito estrictamente no determinista (AFND) definido por la 5-tupla A=<Q, T, g, F, q0>, donde Q es el conjunto de estados, T el alfabeto de símbolos terminales, la relación de transiciones                            ó                                                       (léase: del estado qi mediante el terminal x se va a qj), F son los estados finales o de llegada dentro de Q, q0 es el estado inicial o de partida
A se transforma en AAFD=<QA,T, gA,FA,q0A>', tal que:
VA=P(V)-{{}}, con P(V) que es el conjunto potencia de los vértices de A.
FA={x | }.
gA={<r,x,q> | }.
q0A={q0}.
Luego se eliminan de AAFD todos los estados y sus correspondientes transiciones inalcanzables desde el estado inicial q0A.
CONVERSIÓN
La existencia de este método permite la conversión de cualquier AFND a un AFD equivalente, es decir la eliminación del indeterminismo estricto (el mismo símbolo terminal conduce a más de un estado desde un origen común), aunque no garantiza que sea el AFD equivalente minimal. Para ello deben seguirse otros pasos de reducción del AF.
Otra situación pudiera darse en el caso que se desee, por ejemplo, a partir de una expresión regular se desee obtener su autómata finito determinista, mediante el algoritmo de Thompson se obtiene el AFND-V, luego se procede por el método de la clausura-xi a su conversión a AFND y entonces puede aplicársele al autómata la transformación a AFD.
Ejemplo.
Autómata finito no determinista
que consta de 4 Estados.
		a	X
	D={2} u {-}	={-} u {-}	C={3} u {2}
	conjuntos	a	x
	A={0} u {1,3,2}
	B={1,2} u {3,2}	C={3} u {2}
	B={1,2} u {3,2}
	D={2} u {-}
	C={3} u {2}
	C={3} u {2}
	-----	C={3} u {2}
	D={2} u {-}	-----	C={3} u {2}
Landa: como símbolo de vacío
5
		a	x
	 # A	B	C
	#B	D	C
	#C	-----	C
	D	-----	C
A
D
B
C
a
x
x
a
x
x
Jflap.