Design DPDA to accept languages L={x {a,b} | Na(x) >Nb(x) }, Na(x) >Nb(x) means number of as are greater than number of bs in string x.

8.9kviews

written 8.7 years ago by

teamques10 ★ 70k

• modified 3.8 years ago

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

Marks: 10M

Year: May 2016

theory of computation

ADD COMMENT EDIT

1 Answer

525views

written 8.7 years ago by

teamques10 ★ 70k

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:

$ …

Create a free account to keep reading this post.

and 5 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.