UGC NET CSE | December 2014 | Part 3 | Question: 22

Question

The pushdown automation $M=(\left\{q_{0}, q_{1}, q_{2}\right\}, \left\{a, b\right\}, \left\{0, 1\right\}, \delta, q_{0}, 0, \left\{q_{0}\right\})$ with

$\delta (q_{0}, a, 0)= \left\{(q_{1}, 10)\right\}$

$\delta (q_{1}, a, 1)= \left\{(q_{1}, 11)\right\}$

$\delta (q_{1}, b, 1)= \left\{(q_{2}, \lambda)\right\}$

$\delta (q_{2}, b, 1)= \left\{(q_{2}, \lambda)\right\}$

$\delta (q_{2}, \lambda, 0)= \left\{(q_{0}, \lambda)\right\}$

Accepts the language

• A. $L=\left\{a^{n}b^{m} | n, m \geq 0\right\}$
• B. $L=\left\{a^{n}b^{n} | n \geq 0\right\}$
• C. $L=\left\{a^{n}b^{m} | n, m > 0\right\}$
• D. $L=\left\{a^{n}b^{n} | n > 0\right\}$

Answer 1

D is ans.

L= { aⁿbⁿ | n>0}

null not accept here.

Comments

why not option d

---

its d :)

---

why not option B ?

initial state q0 is also final state, so null must be accepted

please clarify

Answer 2

Ans: B

The no of 'a' and 'b' should be equal..

Comments

there is no transition written for $\epsilon$ from initial state like (q0,$\epsilon$,0) = (q0,$\epsilon$) where q0 is final state then $\epsilon$should not be accepted..isn't??

---

I think u r right... can u tell me what lambda represent here.. ?

δ(q2,b,1)={(q2,λ)}

δ(q2,λ,0)={(q0,λ)}

what is the meaning of these two transition ?