Simulic
Español

Máquinas de estados finitos – semáforos, DFA, NFA y lenguajes regulares

InformáticaAlgoritmos y resolución de problemasEdades 15–16

Cargando…

Usar con mi clase ✨ Personalizar con IA Informar de un problema

Ejecuta paso a paso máquinas de estados de ejemplo (semáforo, máquina expendedora, torniquete) con una secuencia de eventos y observa el estado actual, la salida y una tabla de traza; añade, arrastra y conecta estados para dibujar tu propia máquina. El modo Aceptador comprueba qué palabras acepta un DFA o un NFA (números binarios divisibles por 3, palabras que terminan en ab), con la tabla de transición de estados, una expresión regular y una gramática regular equivalentes y la conversión de NFA a DFA. Una nota compara cada modelo con el sistema real para hablar de abstracción.

Lección: Máquinas de estados finitos: estados, transiciones y salidas; autómatas finitos deterministas y no deterministas; expresiones regulares y gramáticas regulares

Qué muestra

Una máquina de estados finitos tiene un conjunto finito de estados, un estado inicial, un alfabeto de entrada y transiciones de la forma estado + símbolo → estado siguiente. No recuerda nada salvo su estado actual. Una máquina de Mealy produce salidas en sus transiciones, una máquina de Moore asocia las salidas a sus estados y un aceptador responde sí o no: ¿pertenece una palabra a un lenguaje? Los lenguajes que aceptan los autómatas finitos son exactamente los lenguajes regulares, que también describen las expresiones regulares y las gramáticas regulares. Todo NFA (autómata finito no determinista) puede transformarse en un DFA equivalente mediante la construcción de subconjuntos.

Cómo usarla

En el modo Máquina con salida, elige una Máquina de ejemplo y haz clic en Paso o Reproducir para introducir los símbolos de la cinta uno a uno; los botones de símbolo envían eventos adicionales. En el modo Aceptador, elige un Autómata de ejemplo, escribe una Palabra a leer y recórrela paso a paso; luego usa Probar o Listar palabras aceptadas. Abre Editar máquina para añadir, arrastrar y conectar estados, o haz clic en Convertir NFA en DFA.

Parámetros que puedes cambiar

  • Modo Máquina con salida, Aceptador
  • Máquina de ejemplo (modo Máquina con salida) Semáforo, Máquina expendedora, Torniquete
  • Autómata de ejemplo (modo Aceptador) DFA: números binarios divisibles por 3, NFA: palabras que terminan en ab, DFA: palabras que terminan en ab, DFA: número par de unos (bit de paridad)
  • Palabra a leer (vacía = palabra de ejemplo)
  • Velocidad de ejecución 0,5–4 símbolos/s
  • Abrir el panel Editar máquina

Preguntas para explorar

  1. ¿Qué detalles de un semáforo real quedan fuera del modelo y por qué es aceptable?
  2. Siguiéndola estado por estado, ¿acepta el autómata de divisibilidad por 3 la palabra 110?
  3. ¿Por qué el NFA para palabras que terminan en ab necesita menos transiciones que el DFA equivalente?

Simulaciones relacionadas