Autómatas Flashcards
¿Cuál es la capacidad de los autómatas?
Tienen la capacidad de reconocer a los Lenguajes Formales, si tiene la capacidad de reconocer cada palabra del lenguaje y rechazar toda cadena que no es una palabra de ese lenguaje.
¿Cuál es la relación entre GF - LF y autómata?
Una gramática formal genera un lenguaje formal y un autómata reconoce a ese LF.
¿Cuáles son los tipos de autómatas?
El finito, finito con pila y máquina de Turing.
¿Qué autómata reconoce a el Lenguaje Regular?
El autómata finito.
¿Qué autómata reconoce a el Lenguaje Independiente del Contexto?
El autómata finito con pila.
¿Qué autómata reconoce a los LDC y LI?
La máquina de Turing.
¿Qué es un autómata finito (AF)?
Es un modelo matemático de un sistema, que recibe cadenas de caracteres de un alfabeto y determina si esa cadena pertenece al LF que éste reconoce.
¿Cómo están compuestos los AF?
Está compuesto por :
* Un único estado inicial (representado por el signo -)
* Serie de transiciones (→)
* Uno o varios estados finales (representado por el signo +).
¿Cuándo un AF no tiene éxito?
Cuando lee todos los caracteres pero finaliza su actividad en un estado NO final.
Cuando no puede leer todos los caracteres de la cadena.
Cuando la cadena se excede de caracteres que el AF no puede procesar.
¿Cómo se representa un AF que genera un lenguaje regular infinito?
Con un bucle
¿Qué es un AF Determinístico?
Aquellos que para cualquier estado en que se encuentre el autómata en un momento dado, la lectura de un carácter determina, sin ambigüedades, cuál será el estado de llegada en la próxima transición
¿Cómo es la definición formal de AFD?
Es una 5-upla donde :
- Q es un conjunto finito de estados.
- Σ es el alfabeto de caracteres reconocidos por el autómata.
- q0 pertenece Q, estado inicial
- F ⊆ Q conjunto de estados finales.
- T : Q x Σ → Q es la función de transiciones
¿Cómo se representa la función de transición?
Se representa por medio de una tabla de transiciones (TT).
¿Qué es un AFD completo?
Es cuando un AFD tiene exactamente una transición por cada carácter del alfabeto.
(Su TT no tiene huecos).
¿Cuándo un AFD es incompleto?
Cuando su tabla de transiciones tiene huecos.
