The Gateway to Computer Science Excellence
0 votes
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of its stack, $P$ never pops its stack below $x$, no matter what input string $P$ reads from that point on. In that case, the contents of $P’s$ stack at that point cannot affect its subsequent behavior, so $P’s$ subsequent behavior can depend only on $q$ and $x$.)
in Theory of Computation by Veteran (59.2k points) | 5 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,365 answers
105,261 users