Note first that we can perform at most k − 1 Unshift transitions moving a word back to the buffer (because a word can only be moved back to the buffer if it has no head, which can only happen once since Shift is now forbidden).
the new system, shown in Figure 3, differs in four ways from the old system: Configurations are extended with a boolean variable e, keeping track of whether we have seen the end of the input, that is, whether we have passed through a configuration with an empty buffer.