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

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2015

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
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)

ADD COMMENTlink
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.