سوال ۸۹ کنکور ارشد علوم کامپیوتر ۱۴۰۳

اتوماتای پشته‌ای زیر مفروض است. اگر $\alpha = 000011$ و $\beta = 000101010$، کدام‌یک از این دو رشته، توسط این اتوماتا پذیرش می‌شود؟

اتوماتا دارای حالت‌های $q_0, q_1, q_2, q_3, q_4$ است که $q_0$ حالت شروع و $q_4$ تنها حالت پذیرنده است. نماد آغازین پشته $z$ می‌باشد. برچسب گذرها به‌صورت (ورودی، رأس پشته ؛ جایگزین) است، که در آن $\circ$ نماد $0$ و $\lambda$ رشتهٔ تهی است:

• $q_0 \to q_1:\ (0,\, z\ ;\ 0z)$
• $q_1 \to q_1$ (طوقه): $(0,\, 0\ ;\ 00)$
• $q_1 \to q_2:\ (1,\, 0\ ;\ \lambda)$
• $q_2 \to q_3:\ (\lambda,\, 0\ ;\ \lambda)$
• $q_3 \to q_2:\ (1,\, 0\ ;\ \lambda)$
• $q_3 \to q_4:\ (\lambda,\, z\ ;\ \lambda)$