In the CFG$->$PDA conversion we maintained the invariant that $$ Choice $1$ of $4$: the input concatenated with the stack contents is a derivation string Choice $2$ of $4$: the stack contains a derivation string Choice $3$ of $4$: the input read so far is a derivation string Choice $4$ of $4$: the input read so far concatenated with the stack contents is a derivation string $$As a reminder, a derivation string is any one of the strings in the intermediate steps of a derivation $$ S$...$w$,$ including $$ S and w