Gate Sample 2018

Question

Consider PDA = M = ({q0, q1}, {a, b}, {a, z0}, δ, q0, z0, φ) which accepts by empty stack
δ: (q0, a, z0) = (q0, az0)
(q0, a, a) = (q0, aa)
(q0, b, a) = (q1, a)

(q1, b, a) = (q1, a)
(q1, a, a) = (q1, ε)
(q1, ε, z0) = (q1, ε)
Which one of the following strings is accepted by the above PDA?
(s1) aaa
(s2) aabbaa
(s3) aba
(s4) aaab

(a) Only s2, s3 and s4 (b) Only s1
(c) Only s2 and s3 (d) Only s2

Solution: Option (c)
Explanation:
The transitions given corresponds to the language ={/ >0,>0}

how ? in transition 4th line (q1, b, a) = (q1, a) we dont perform pop operation for a then how is explanation correcT?

Answer 1

Given PDA accepts lang = {a^n b⁺ a^n}

We do not perform POP operation (q1, b, a) = (q1, a) , we just bypassing "b"

only S2 and S3 are accepted by given PDA.

Comments

Correct