Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)

Question

Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.

Answer 1

Language acceptance by CFL is undecidable.

As easy as that.

Only membership, emptiness and finiteness only decidable.

Answer 2

let’s assume w= 01

for ww, it will be 0101

Since the first and the last symbol is different.Hence, the problem is undecidable