0
Construct PDA accepting the language. L = {anbn|n>0}.

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2015

0  upvotes
0

PDA is used for recognizing CFL which is generated by CFG.

Logic:

For each ‘a’ push 1X

For each ‘b’ pop 1X

Implementation:

$M = (Q, Σ, Ґ, δ, q_0, z_(0 ), F )$

$Q = {q_0, q_1, q_f}$

$Σ= {a, b}$

$Ґ = {X, R}$

$q_0 = q_0$

$z_0 = R$

$F = {q_f}$

δ:

$δ (q_0, a, R) = {(q_0, XR)}$

$δ (q_0, a, X) = {(q_0, XR)}$

$δ (q_0, b, X) = {(q_1, €)}$

$δ (q_1, b, X) = {(q_1, €)}$

$δ (q_1, €, R) = {(q_f, R)}$

enter image description here

Example:

$(q_0, aabb, R)$

$| - (q_0, abb, XR)$

$| - (q_0, bb, XXR)$

$| - (q_1, b, XR)$

$| - (q_1, €, R)$

$| - (q_f, €, R)$

(Accept)

0  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More