1
$\begingroup$

"It is a well known result that every PDA with acceptance condition of an empty stack and reachability of a final state can be transformed to an equivalent PDA with acceptance condition requiring only reachability of a final state. Transform PDA ____ to an equivalent PDA with acceptance requiring only reachability of a final state."

I'm just a bit confused on what steps I have do to. My thought process is...final state + empty stack acceptance is a subset of just a final state acceptance? When I try to 'transform' my PDA, it ends up looking exactly the same as the original.

$\endgroup$
1
$\begingroup$

Given a PDA $M$, you can define the following associated languages:

  • The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state with an empty stack. We denote this language by $L_1(M)$.

  • The language of all words $w$ such that there is a computation path for the PDA on $w$ in which it ends at a final state. We denote this language by $L_2(M)$.

The two languages are not always the same, that is, it could well be that $L_1(M) \neq L_2(M)$. You have to show that for each PDA $M$ there is another PDA $M'$ such that $L_1(M) = L_2(M')$.

$\endgroup$
  • $\begingroup$ How do I do that? That sounds like induction to me. However, I have to transform a PDA by empty + final acceptance to just a PDA with final state acceptence. So say I have a PDA which represents language a^nb^n. How would I be able to show this as just a final state acceptance, rather than final state + empty stack? $\endgroup$ – Jake Mar 21 '17 at 1:55
  • $\begingroup$ Induction is not a good idea in this case. You will use it perhaps to prove the equivalence of the two machines, but not to construct $M'$ from $M$. $\endgroup$ – Yuval Filmus Mar 21 '17 at 8:35

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.