es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Cómo definir delta en un APD

15 Jul, 2023 Programación

Estoy un poco confundido/a acerca de los APD (autómatas con pila) y cómo definir la tupla. Tengo el lenguaje L = { 0^n1^n | n >= 0 } y sé que los APD son una sextupla con Q, sigma, gamma, delta, q0 y F. Sé cómo definir todos excepto delta.

Q = ['q1', 'q2', 'q3', 'q4']
sigma = ['0', '1']
gamma = ['0', '$']
delta = ?
q0 = 'q1'
F = ['q1', 'q4']

¿Alguien puede ayudarme a entender cómo se define delta?

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Delta es la función de transición del autómata de empuje (PDA, por sus siglas en inglés) y asigna el estado actual, el símbolo de entrada y el símbolo en la parte superior de la pila al siguiente estado y la operación de pila a realizar. En otras palabras, delta define el comportamiento del PDA.

    En el caso del lenguaje L = { 0^n1^n | n >= 0 }, el PDA se puede definir de la siguiente manera:

    • Q = { q1, q2, q3, q4 }: conjunto de estados
    • Sig = { 0, 1 }: alfabeto de entrada
    • Gam = { 0, $ }: alfabeto de pila, donde $ es el símbolo en el fondo de la pila
    • Delta: función de transición

    Delta se puede definir de la siguiente manera:

    • δ(q1, 0, $) = (q2, 0$): leer 0, empujar 0 en la pila y moverse al siguiente estado q2
    • δ(q2, 0, 0) = (q2, 00): leer 0 y empujar 0 en la pila
    • δ(q2, 1, 0) = (q3, $): leer 1, sacar 0 de la pila y moverse al siguiente estado q3
    • δ(q3, 1, 0) = (q3, ε): leer 1 y sacar 0 de la pila
    • δ(q3, ε, $) = (q4, $): leer ε y moverse al siguiente estado q4 si la pila contiene solo el símbolo en el fondo $

    donde ε denota la cadena vacía.

    • q0 = q1: estado inicial
    • F = { q1, q4 }: conjunto de estados de aceptación

    En resumen, delta define las reglas del PDA para leer símbolos de entrada, modificar la pila y cambiar de estado en función del estado actual, el símbolo de entrada y el símbolo en la parte superior de la pila.

Comments are closed.