Peter Linz Edition 4 Exercise 7.3 Question 10 (Page No. 200)

Question

While the language in Exercise 9 is deterministic, the closely related language $L =$ {$ww^R : w ∈${$a,b$}$^*$} is known to be nondeterministic. Give arguments that make this statement plausible.

Answer 1

In Exercise 9 problem the automata was deterministic because we knew when we need to start popping out from the stack but here we don't know what is the midpoint of the given string and from which step we need to start popping elements from the stack.

Here we have to find the center using brute force kind of approach , whenever the top of stack element and the input element are same then that input element could be either the center of string or could be the just another element so we could either push that element in stack or we could then go to another state and start popping elements, this is a non deterministic move as we can't say which move we should  take and hence the given language is non-deterministic language.