11,171 views
0 votes
0 votes
Which of the following is accepted by an NDPDM  but not by DPDM

a)All strings in which a given symbol is present at  least twice

b)Even length palindromes

c)Strings ending with a particular terminal

d)Odd length palindromes

2 Answers

1 votes
1 votes

● Idea: Push the first half of the symbols on to the stack, then verify that the second half of the symbols match.

● Nondeterministically guess when we've read half of the symbols.

so b is ans.

https://www.cs.wcupa.edu/rkline/fcs/pdas.html

http://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/17/Small17.pdf

https://people.cs.clemson.edu/~goddard/texts/theoryOfComputation/7.pdf

1 votes
1 votes

a) Suppose that symbol is 'a'
Got first 'a' push it. Go next state.
Ignore other symbols. Got another 'a'
Now go to final state. If more 'a' comes no problem.
DPDA

b) Even length palindrome.
It totally depends on the type.

abb   bba  (NPDA)
abb x bba  (DPDA)  (Do not call it odd length palindrome)

c) Ending with a particular terminal.
It is under regular language. DPDA too.
 

d) Odd length palindrome.

abb a bba (NPDA only)
How can you know when that middle one will come?
I have not seen ussages of x in these.

Please  tell if I went wrong somewhere with proper explanations.

Related questions

1 votes
1 votes
1 answer
1
ashutoshaay26 asked Aug 15, 2017
1,122 views
What is main difference between Deterministic Push down automata and simple Push down automata ?
1 votes
1 votes
0 answers
2
Bencher Last asked Jul 21, 2017
231 views
What will be the DPDA of a language L = {aibj|for every prefix of the string |n(a)-n(b)|≤2 where n(a)=number of a & n(b)=number of b}
0 votes
0 votes
1 answer
3
hrcule asked Mar 21, 2018
663 views
Is true..? In an unambiguous grammar every string has exactly one derivation.