AUTOMATAS
Máquina que realiza tareas siguiendo instrucciones paso a paso.
¿Qué es un algoritmo?
Los símbolos que puede leer el autómata.
¿Qué representa el alfabeto?
Deterministic Finite Automaton.
¿Qué significa DFA?
Una secuencia de símbolos del alfabeto.
¿Qué es una cadena?
Modelo abstracto que usa estados y transiciones para procesar entradas.
¿Qué es un autómata finito?
El estado donde comienza la evaluación.
¿Qué es el estado inicial?
Nondeterministic Finite Automaton
¿Qué significa NFA?
Cualquier cadena con cantidad par de 1’s.
¿Qué cadena acepta un autómata que reconoce número par de 1’s?
Permite que un autómata decida si una cadena pertenece a un lenguaje.
¿Qué es el proceso de aceptación?
Indica el cambio de estados según el símbolo leído.
¿Qué es la función de transición?
En un DFA cada símbolo tiene una sola transición; en un NFA puede haber varias.
Diferencia principal entre DFA y NFA.
No, no con memoria limitada
¿Puede un autómata reconocer palíndromos?
Tipo de autómata que usa una memoria tipo pila.
¿Qué es un autómata de pila?
Estados de aceptación donde la cadena es válida.
¿Qué son los estados finales?
Sí, siempre.
¿Todo NFA puede convertirse en un DFA?
Cadenas que terminan en “01”.
Ejemplo de lenguaje regular.
Máquina teórica más poderosa, capaz de simular cualquier algoritmo.
¿Qué es la Máquina de Turing?
Conjunto de estados, alfabeto, transiciones, estado inicial y estados finales.
¿Qué elementos forman un autómata finito?
El NFA.
¿Cuál suele tener menos estados tras la conversión?
No puede reconocer lenguajes que requieren memoria ilimitada.
¿Qué limita a un autómata finito?