L={x∈{a, b}* | Na(x)>Nb(x)}, Na(x)>Nb(x) means number of a's are greater than number of b's in string x:

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,Σ,Ґ,δ,q0,z(0),F)M=(Q,Σ,Ґ,δ,q0,z(0),F)

Q=q0,q1,qfQ=q0,q1,qf

Σ=a,bΣ=a,b

Ґ=X,RҐ=X,R

q0=q0q0=q0

z0=Rz0=R

F=qfF=qf

δ:

δ(q0,a,R)=(q0,XXR)δ(q0,a,R)=(q0,XXR)

δ(q0,a,X)=(q0,XXX)δ(q0,a,X)=(q0,XXX)

δ(q0,b,X)=(q1,€)δ(q0,b,X)=(q1,€)

δ(q1,b,X)=(q1,€)δ(q1,b,X)=(q1,€)

δ(q1,€,R)=(qf,R)δ(q1,€,R)=(qf,R)

Example :

(q0,aaabbbbbb,R)(q0,aaabbbbbb,R)

|−(q0,aabbbbbb,XXR)|−(q0,aabbbbbb,XXR)

|−(q0,abbbbbb,XXXXR)|−(q0,abbbbbb,XXXXR)

|−(q0,bbbbbb,XXXXXXR)|−(q0,bbbbbb,XXXXXXR)

|−(q1,bbbbb,XXXXXR)|−(q1,bbbbb,XXXXXR)

|−(q1,bbbb,XXXXR)|−(q1,bbbb,XXXXR)

|−(q1,bbb,XXXR)|−(q1,bbb,XXXR)

|−(q1,bb,XXR)|−(q1,bb,XXR)

|−(q1,b,XR)|−(q1,b,XR)

|−(q1,€,R)|−(q1,€,R)

|−(qf,€,R)|−(qf,€,R)

(Accept)