Intro to theory of Computation by Sipser (pg 118)
I'm reading his explanation on the proof: "If a language is context free, then some PDA recognizes it"
But I'm having trouble understanding one of the examples.
Here, Sipser gives an example of the behaviour of the stack with an intermediate string on a PDA P.
P representing the intermediate string "01A1A0"
The following is an informal description of P.
Place the marker symbol $ and the start variable on the stack.
Repeat the following steps forever.
a) If the top of stack is a variable symbol A, nondeterministically select one of the rules for A and substitute A by the string on the right-hand side of the rule.
b) If the top of stack is a terminal symbol a, read the next symbol from the input and compare it to a. If they match, repeat. If they do not match, reject on this branch of the nondeterminism.
c) If the top of stack is the symbol $, enter the accept state. Doing so accepts the input if it has all been read.
For b), why is it that we need to read next symbol of input for the comparison? I think it's because the following input symbols will correspond to these terminals in the stack.
In b), "if they match, repeat." refers to repeating the entire process for another a or the same a but taking the next symbol from input?
Also, for a) Sipser did not mention any matching of input to the substituted string as he did for b). If this substituted string doesn't match the input, wouldn't this result in a rejection? I assume this has something to do with the non-deterministic selection.
Any clarification will be much appreciated.
A nondeterministic PDA uses its stack to derive a string in its grammar, and it reads the input to compare it to the string on the stack. Thanks to nondeterministism, the PDA will try the right derivation---if presented with a string in its language.
Keeping this in mind helps us to answer your questions. In part (b), the PDA is checking its guess against the actual input. The guess is built on the stack so that the end of the string is at the bottom of the stack. Hence the $i$-th terminal symbol popped from the stack is the $i$-th letter of the guessed word. It must be compared with the $i$-th letter of the input word.
In case of mismatch, the guess was wrong. In case of match, this character has been checked, it matches, and will not be looked at again. The copy on the stack is popped, while the one in the input is simply left behind by the read head.
In (a), the PDA is building its guess. It doesn't compare a nonterminal symbol to an input letter. Instead, it picks a rule that has that nonterminal symbol as left-hand side.
Let's see this at work on a very simple example. Suppose the grammar is simply
$$ S \rightarrow 1S0 \mid \epsilon \enspace, $$
while the input string is $1100$. With $\$$ as end-of-stack symbol, the initial stack is $S\$$ (top of the stack to the left and bottom to the right). When the PDA pops $S$, it "magically" chooses to replace it with $1S0$. Therefore the new stack is $1S0\$$.
Now the top of the stack is a terminal, which is compared to the first letter of $1100$. A match is found; hence the PDA continues with stack $S0\$$ and unread input $100$.
Next the PDA again decides to replace the $S$ at the top of the stack with $1S0$. The resulting stack is $1S00\$$. On the next step, it matches the $1$ at the top of the stack to the front of the input. There's another match, which leaves the stack as $S00\$$ and the unread input as $00$.
On the next iteration, the PDA decides to replace the $S$ at the top of the stack with the empty string. At this point the stack is $00\$$ and the remaining input is $00$. Two more steps result in two more matches and lead to success.