1 votes 1 votes 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. Theory of Computation michael-sipser theory-of-computation pushdown-automata decidability proof + – admin asked Oct 20, 2019 edited Oct 20, 2019 by Lakshman Bhaiya admin 556 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Language acceptance by CFL is undecidable. As easy as that. Only membership, emptiness and finiteness only decidable. shashankrustagi answered Dec 10, 2020 shashankrustagi comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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 Anshu Rathore answered Jan 18, 2021 Anshu Rathore comment Share Follow See all 0 reply Please log in or register to add a comment.