Example 3.3.3 Now we consider the language L = {w/w {a,b}", w has the same number of a's and b's). The pushdown automaton A that recognizes this language is an "extension" of the automaton in Example 3.3.1. If the number of a's and b's in the input read so far is equal, the stack is empty. If there are more a's than b's, the excess is pushed onto the stack where reading a b from the input results then in popping one a from the stack. Analogously, if there are more b's than a's, it is the b's that go on the stack to be popped off against a's from the input. To implement this idea, the automaton must be able to recognize when the stack becomes empty so it can "change its mind" and start to fill the stack by either a's or b's all over again. The empty stack test can be achieved by adding a special marker cer that is placed on the bottom of the stack at the very beginning of the automaton's operation. The marker c is used only in this situation. Now the automaton is able to recognize if it has reached the bottom of the stack. As in the previous example, we assume that s = 80 and F = {f}; the set of transitions is (1) (8,e,e), (9,0)) (2) (g, a,c), (q, ac)) (3) ((q, a, a),(g, aa)) (4) ((q,a,b), (q, e)) (5) ((q,b,c), (q, bc)) (6) ((q,b,b), (q, bb)) (7) ((q, b, a),(g, e)) (8) (lq,e,c), (f.e)) Being fed the input abbbaaaabb, the automaton first applies transition 1 to place the marker on the bottom of the stack. Then it uses transition 2 to push the first a onto the stack. Then transition 7 is applied to pop the stack. Now the stack is empty, and the automaton applies transition 5 to push the first b and transition 6 to push the next b onto the stack. Then it applies transition 4 two times to clear the b's from the stack. Now A starts to push the rest of the a's onto the stack, applying transitions 2 and 3. Then two applications of transition 7 clear the stack of a's, and the automaton uses transition 8 to enter the favorable state. This operation is illustrated in Figure 3.5. End Example Exercise 3.19 Trace the pushdown automaton of Example 3.3.3 on the following strings: a) aabbb b) aabababb