1
$\begingroup$

This proof is from the book "Introduction to Languages and the Theory of Computation" by John C. Martin.

My question is from the pink part at the second page:

It follows in particular that no sequence of moves can cause M to empty its stack.

and further, it talks about $y_x$ that is my second question. I can't understand what $y_x$ is.

I'll appreciate it if someone please describe me the whole proof.

First page of the proof Second page of the proof

$\endgroup$
  • $\begingroup$ "For an arbitrary $x$, there is a string $y_x$ such that of all the possible strings $xy$, $xy_x$ is one whose processing by $M$ produces a configuration with minimum stack height." $\endgroup$ – Hendrik Jan Dec 14 '19 at 16:30
1
$\begingroup$

No sequence of moves may empty the stack, this is seen as follows. Since the PDA is deterministic, its computation is determined by its input. So we have to argue that the computation on $x$ will not empty the stack. If it would empty the stack, then the PDA blocks, and can no longer continue. But observe that $xx^R$ is a palindrome, so there should be an accepting computation on $xx^R$. This implies that the computation on the prefix $x$ should not block.

Your second question. For input $x$ we can look at all continuations $xy$. For each $y$ determine the stack height that is obtained. We choose an $y$ for which this is minimal and call this specific string $y_x$ (to indicate it depends on $x$).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.