Considere el NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, donde (como de costumbre convención) Q es el conjunto de estados, Σ es el alfabeto de entrada, Γ es el alfabeto de pila, δ es la función de transición de estado, q0 es el estado inicial, ⊥ es el símbolo de pila inicial y F es el conjunto de estados de aceptación. La transición de estado es la siguiente: ¿Cuál de las siguientes secuencias debe seguir a la string 101100 para que el autómata acepte la string total? (A) 10110 (B) 10010 (C) 01010 (D) 01001 Respuesta: (B) Explicación:
En el estado q0 para ‘1’, se presiona un ‘1’ y para un ‘0’ se presiona un ‘0’. En el estado q1, para un ‘0’ se abre un ‘1’ y para un ‘1’ se abre un ‘0’. Entonces, el PDA dado acepta todas las strings de la forma x0x’r o x1x’r o xx’r, donde x’r es el reverso del complemento a 1 de x.
La string dada 101100 tiene 6 letras y nos dan 5 strings de letras. Entonces, x0 está hecho, con x = 10110. Entonces, x’r = (01001)r = 10010.
Por lo tanto, la opción B es correcta.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA