ESTADOS SIGNIFICATIVOS Y NO SIGNIFICATIVOS EN UN AUTÓMATA FINITO NO DETERMINISTA

UNIVERSIDAD SAN CARLOS DE GUATEMALA
FACULTAD DE INGENIERÍA
ESCUELA DE CIENCIAS Y SISTEMAS
LENGUAJES FORMALES DE PROGRAMACIÓN
SECCIÓN B+
ING. CRISTIAN EDUARDO LAVARREDAESTADOS SIGNIFICATIVOS Y NO SIGNIFICATIVOS
EN UN AUTÓMATA FINITO NO DETERMINISTA
















Nombre: José Daniel Chavarría Esteban
Carnet:201213058





16 de Septiembre del 2013
Estados significativos y no significativos en
un Autómata Finito no Determinista

Autómata finito no determinista (AFN): es unautómata el cual tiene una cantidad finita de estados, pero a diferencia de los autómatas finitos deterministas, incluye transiciones epsilon y la posibilidad de ir de salir de un estado ados o más estados diferentes por medio de un símbolo de entrada igual. Esto último causa confusión ya que no se define lo que ocurre al entrar un símbolo específico. En resumenpodemos mencionar las siguientes características de un AFN:

No determinístico.
Transiciones no definidas.
Posibilidad de transitar de un estado a otro sin necesidad de leer unsímbolo de entrada.


Estados significativos en un AFN: a un estado le llamamos significativo, en un AFN, si tiene una transición de salida que no sea epsilon. Los estadossignificativos corresponden a un operador específico en la expresión regular y corresponden directamente a las posiciones en la expresión regular que contienen símbolos del alfabeto.

Estadosno significativos en un AFN: se llama asi a los estados que únicamente tienen salidas de transicion epsilon y los que no cumplen las características de un estado significativo. Altener únicamente salidas epsilon los hace no significativos ya que estas transiciones no describen o no proporcionan suficiente información acerca del comportamiento del autómata.