Estudiante

La teoría de autómatas es una rama de las ciencias de la computación que estudia matemáticamente maquinas abstractas y problemas que estas son capases de resolver. La teoría de autómatas estáestrechamente relacionada con la teoría de lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capases de reconocer.
Autómata Finito Se define entérminos de sus estados, la entrada que acepta y su reacción ante la misma. Hay autómatas finitos de 2 tipos: Deterministas y no Deterministas, dependiendo de cómo se defina la capacidad para cambiar elestado. Funcionamiento de los autómatas finitos Consiste en ir pasando de un estado a otro, a medida que va recibiendo los caracteres de la palabra de entrada. Simplemente hay que pasar de estado a estadosiguiendo las flechas de transiciones para cada carácter de la palabra de entrada, empezando por el estado inicial. Este proceso puede llevarse a cobo en los diagramas de estado y el camino recorridose visualiza como una trayectoria.

Autómata finito no determinista (AFND)
Los estados de un autómata de este tipo pueden, o no, tener una o más transiciones por cada símbolo del alfabeto. Elautómata acepta una palabra si existe al menos un camino desde el estado q0 a un estado final F etiquetado con la palabra de entrada. Si una transición no está definida, de manera que el autómata no puedesaber como continuar leyendo la entrada, la palabra es rechazada.
Autómata finito no determinista con transiciones ε (AFND-ε)
Además de ser capaz de alcanzar más estados leyendo un símbolo, permitealcanzarlos sin leer ningún símbolo. Si un estado tiene transiciones etiquetadas con , entonces el AFND puede encontrarse en cualquier de los estados alcanzables por las transiciones , directamente oa través de otros estados con transiciones . El conjunto de estados que pueden ser alcanzados mediante este método desde un estado q, se denomina la clausura de q.




Antecedentes
En los...