BrainTok
ENESIT

Teoría de la computación: Autómatas finitos y lenguajes regulares · Autómatas finitos deterministas

Cómo funcionan los autómatas finitos deterministas, qué puede y qué no puede seguir su memoria finita y cómo diseñar autómatas pequeños.

Teoría de la computación · 28 preguntas

Prueba 3 preguntas

1. Para cada estado y símbolo de entrada, ¿cuántas transiciones define un autómata finito determinista (AFD)?

  1. Como máximo una
  2. Al menos una
  3. Exactamente una
Ver la respuesta

Respuesta: Exactamente una

Ser determinista significa que la función de transición asigna a cada par (estado, símbolo) exactamente un estado siguiente, así que el recorrido de la máquina sobre cualquier entrada queda completamente fijado.

2. Un AFD pasa por un estado de aceptación a mitad de una cadena, pero termina en un estado de no aceptación. ¿Se acepta la cadena?

  1. Sí, basta con llegar una vez a la aceptación
  2. No, solo cuenta el estado final
  3. Solo si la cadena no es vacía
Ver la respuesta

Respuesta: No, solo cuenta el estado final

La aceptación depende únicamente del estado en que queda el AFD después de leer el último símbolo; los estados visitados en el camino no importan.

3. Además de saber en qué estado se encuentra, ¿qué memoria tiene un AFD?

  1. Una cinta de lectura y escritura
  2. Ninguna en absoluto
  3. Un único contador
Ver la respuesta

Respuesta: Ninguna en absoluto

La única memoria de un autómata finito es cuál de sus finitos estados ocupa, y por eso no puede contar sin límite.

El resto del quiz, unas pocas preguntas a la vez

BrainTok te hace unas preguntas de quizzes como estos antes de abrir las apps que elijas, y tu tiempo de pantalla se vuelve aprendizaje. Para iPhone.

Únete a la beta

Más quizzes de Ingeniería en Sistemas y Computación