in Theory of Computation
5,789 views
0 votes
0 votes

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?

in Theory of Computation
5.8k views

1 Answer

1 vote
1 vote

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.

1 comment

Correct
0
0

Related questions