Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: May 2016

In DPDA there is only one move in every situation. A DPDA is less powerful than NPDA.

Every context free language cannot be accepted by a DPDA

Logic:

L = { x {a, b}* | Na(x) > Nb(x) }, Na(x) > Nb(x) means number of a's and b’s.

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, XXR)}$

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

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

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

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

Example:

$(q_0, aaabbbbbb, R)$

$| - (q_0, aabbbbbb, XXR)$

$| - (q_0, abbbbbb, XXXXR)$

$| - (q_0, bbbbbb, XXXXXXR)$

$| - (q_1, bbbbb, XXXXXR)$

$| - (q_1, bbbb, XXXXR)$

$| - (q_1, bbb, XXXR)$

$| - (q_1, bb, XXR)$

$| - (q_1, b, XR)$

$| - (q_1, €, R)$

$| - (q_f, €, R)$

(Accept)