Example 7.4
Construct an npda for the language
As in Example 7.2, the solution to this problem involves counting the number of
a’s and b’s, which is easily done with a stack. Here we need not even worry
about the order of the a’s and b’s. We can insert a counter symbol, say 0, into the
stack whenever an a is read, then pop one counter symbol from the stack when a
b is found. The only difficulty with this is that if there is a prefix of w with more
b’s than a’s, we will not find a 0 to use. But this is easy to fix; we can use a
negative counter symbol, say 1, for counting the b’s that are to be matched
against a’s later. The complete solution is given in the transition graph in Figure
7.3.
Figure 7.3
In processing the string baab, the npda makes the moves
and hence the string is accepted.
Example 7.5
To construct an npda for accepting the language
L = { ww R : w ∈ {a, b} + }