Estaba trabajando en máquinas de Turing, luego tuve un problema con alguien.

a^m . a^3n . b^n

¿Cómo diseñar un diagrama de estado para esta máquina? ¿Puedes por favor ayudarme?

1
Daymnn 24 jun. 2020 a las 13:23

2 respuestas

La mejor respuesta

Asumiendo que no hay relación entre myn, aquí está la estrategia:

  1. Verifique que todo hasta el primer período sea un a. Si ve algo más antes de llegar al primer período, detenga el rechazo. A menos que se asuma m > 0, está bien ver un punto como el primer símbolo de entrada.

  2. Si no ve a s restantes de la segunda sección, verifique que no queden b s restantes en la tercera sección y, si es así, detenga la aceptación. De lo contrario, si quedan b s, detenga el rechazo.

  3. Si quedan a s en la segunda sección, tache tres de los a s. Si no hay al menos tres a s para tachar, detener-rechazar. Si los hay, entonces tache uno b. Si no quedan b s restantes para tachar, detenga el rechazo. Si hay un b, regrese a la segunda sección y continúe con el paso 2 hasta que detenga o acepte o detenga el rechazo.

Ejemplos:

aa.aaaaaa.bb => aa.xxxaaa.xb => aa.xxxxxx.xx => halt-accept
aa.aaaaa.bb => aa.xxxaa.xb => halt-reject
aa.aaaaaa.bbb => aa.xxxaaa.xbb => aa.xxxxxx.xxb => halt-reject
aa.aaaaaa.b => aa.xxxaaa.x => aa.xxxxxx.x => halt-reject
ba.aaaaaa.bb => halt-reject

Los estados podrían verse así:

state    tape    state'    tape'    direction    comment

q0       a       q0        a        right        read a's until you see
q0       .       q1        .        right        a period, crash otherwise

q1       a       q2        x        right        if you see a's, cross off
q1       x       q1        x        right        the 1st of 3. skip x's and
q1       .       q8        .        right        if you see . check for no b's

q2       a       q3        x        right        read the 2nd of 3 a's

q3       a       q4        x        right        read the 3rd of 3 a's

q4       a       q4        a        right        skip over any remaining a's
q4       .       q5        .        right        to get to the 2nd .

q5       b       q6        x        left         cross off one b for the 3 a's
q5       x       q5        x        right        skip over any x's

q6       x       q6        x        left         skip over any x's and
q6       .       q7        .        left         go back to 2nd .

q7       a       q7        a        left         skip over any a's and go
q7       x       q1        x        right        back to last x in 2nd section

q8       x       q8        x        right        skip over any x's in 3rd part
q8       #       halt-acc  #        same         if no more b's then #a = 3*#b
1
Patrick87 24 jun. 2020 a las 12:32

Como su otra pregunta se cerró, aquí hay una respuesta.

Aquí está nuestra estrategia:

Intenta tachar tres a's. Si tenemos éxito, tache una b, y luego repita el proceso. Si fallamos en cualquiera de los anteriores, asegúrese de que no haya más b; de lo contrario, suspenda-acepte, de lo contrario, detenga-rechace.

Ejemplos:

aabaaaba => xxbxaaba => xxxxaaba => xxxxxxbx => xxxxxxxx => halt-accept
aa => xx => halt-accept
aaa => xxx => halt-accept

Los estados podrían verse así:

state    tape    state'    tape'    direction    comments

q0       a       q1        x        right        read the 1st of 3 a's
q0       b       q0        b        right        skip any b's
q0       x       q0        x        right        skip any crossed-off
q0       #       q6        #        left         if no a's make sure no b's

q1       a       q2        x        right        read the 2nd of 3 a's
q1       b       q1        b        right        skip any b's
q1       x       q1        x        right        skip any crossed-off
q1       #       q6        #        left         if just one a make sure no b's

q2       a       q3        x        left         read the 3rd of 3 a's
q2       b       q2        b        right        skip any b's
q2       x       q2        x        right        skip any crossed-off
q2       #       q6        #        left         if just two a's make sure no b's

q3       a       q3        a        left         rewind to the front of the
q3       b       q3        b        left         tape, skipping all a's, b's
q3       x       q3        x        left         and x's until we get to the
q3       #       q4        #        right        blank at the front

q4       a       q4        a        right        skip any a's
q4       b       q5        x        left         cross off one b
q4       x       q4        x        right        skip any x's
q4       #       halt-acc  #        same         accept if no more b's found

q5       a       q5        a        left         rewind the tape, skipping any
q5       b       q5        b        left         a's, b's and x's until we get
q5       x       q5        x        left         to the blank at the front of
q5       #       q0        #        right        the tape; then repeat from q0

q6       a       q6        a        left         just verify no more b's on
q6       b       halt-rej  b        same         the tape; we're starting at
q6       x       q6        x        left         the end so scan backwards
q6       #       halt-acc  #        same
1
Patrick87 24 jun. 2020 a las 13:30