PUERTA | PUERTA 2006 | Pregunta 33

Considere el autómata pushdown (PDA) debajo del cual se ejecuta el alfabeto de entrada (a, b, c). Tiene el alfabeto de pila {Z ₀ , X} donde Z ₀ es el marcador de la parte inferior de la pila. El conjunto de estados de la PDA es (s, t, u, f} donde s es el estado inicial y f es el estado final. La PDA acepta por estado final. Las transiciones de la PDA que se dan a continuación se representan de manera estándar Por ejemplo, la transición (s, b, X) → (t, XZ ₀ ) significa que si la PDA está en el estado s y el símbolo en la parte superior de la pila es X, entonces puede leer b de la entrada y muévase al estado t después de abrir la parte superior de la pila y empujar los símbolos Z ₀ y X (en ese orden) en la pila
(s, a, Z ₀ ) → (s, XXZ ₀ )
(s, ϵ, Z ₀ ) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t ,.ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z ₀ ) → (f, ϵ)

El lenguaje aceptado por la PDA es
(A) {a ^l b ^m c ⁿ | l = metro = norte}
(segundo) {un ^l segundo ^metro do ^norte | l = metro}
(C) {a ^l segundo ^metro c ^norte | 2l = m+n} ⁽
D) {a ^l segundo ^metro c norte | m=n} Respuesta: (C) Explicación: Cada entrada ‘a’ inserta dos X en la pila y cada X puede ser consumida por ‘b’ o ‘c’ solamente. En la entrada ‘a’ no hay ninguna regla que dé ϵ. Así, para cada ‘a’, la terminación se realiza mediante ‘b’ o ‘c’ o ambos.

Ejemplo:
Entrada:
a ³ b ² c ⁴
Pila:Z ₀
Después de tres a:
Pila:
XXXXXXZ ₀
Después de dos b:
Pila:
XXXZZ ₀
Después de cuatro c:
Puede llegar al estado final.
a ³ b ² c ⁴ también se acepta aquí.
Cuestionario de esta pregunta