3.2  Pushdown Transducers

      Pushdown Transducers
      Configurations and Moves of Pushdown Transducers
      Determinism and Nondeterminism in Pushdown Transducers
      Computations of Pushdown Transducers
      From Recursive Finite-Domain Programs to Pushdown Transducers
      From Pushdown Transducers to Recursive Finite-Domain Programs
      Pushdown Automata

In general, recursion in programs is implemented by means of a pushdown store, that is, a last-in-first-out memory. Thus, it is only natural to suspect that recursion in finite-domain programs implicitly allows an access to some auxiliary memory. Moreover, the observation makes it also unsurprising that the computations of recursive finite-domain programs can be characterized by finite-state transducers that are augmented with a pushdown store. Such transducers are called pushdown transducers.

 Pushdown Transducers

Each pushdown transducer M can be viewed as an abstract computing machine that consists of a finite-state control, an input tape, a read-only input head, a pushdown tape or pushdown store, a read-write pushdown head, an output tape, and a write-only output head (see Figure 3.2.1). Each move of M is determined by the state of M, the input to be consumed, and the content on the top of the pushdown store. Each move of M consists of changing the state of M, reading at most one input symbol, changing the content on top of the pushdown store, and writing at most one symbol into the output.

Figure 3.2.1 Schema of a pushdown transducer.

Example 3.2.1    A pushdown transducer M can compute the relation { (aⁱbⁱ, cⁱ) | i 1 } by checking that each input has the form a ab b with the same number of a's as b's, and writing that many c's. The computations of M can be in the following manner (see Figure 3.2.2).

Figure 3.2.2 A description of how a pushdown transducer can compute the relation { (aibi, ci) | i 1 }.

Initially the pushdown store is assumed to contain just one symbol, say, Z₀ to mark the bottom of the pushdown store. M starts each computation by reading the a's from the input tape while pushing them into the pushdown store. The symbols are read one at a time from the input.

Once M is done reading the a's from the input, it starts reading the b's. As M reads the b's it retrieves, or pops, one a from the pushdown store for each symbol b that it reads from the input. In addition, M writes one c to the output for each symbol b that it reads from the input.

M accepts the input if and only if it reaches the end of the input at the same time as it reaches the symbol Z₀ in the pushdown store. M rejects the input if it reaches the symbol Z₀ in the pushdown store before reaching the end of the input, because in such a case the input contains more b's than a's. M rejects the input if it reaches the end of the input before reaching the symbol Z₀ in the pushdown store, because in such a case the input contains more a's than b's.

Formally, a mathematical system M consisting of an eight-tuple <Q, , , , , q₀, Z₀, F> is called a pushdown transducer if it satisfies the following conditions.

Q

is a finite set, where the elements of Q are called the states of M.

, and

are alphabets. is called the input alphabet of M, and its elements are called the input symbols of M. is called the pushdown alphabet of M, and its elements are called the pushdown symbols of M. is called the output alphabet of M, the elements of which are called the output symbols of M.

is a relation from Q × ( {}) × ( {}) to Q × * × ( {}). is called the transition table of M, the elements of which are called the transition rules of M.

q₀

is an element in Q, called the initial state of M.

Z₀

is an element in , called the bottom pushdown symbol of M.

F

is a subset of Q. The states in the subset F are called the accepting , or final, states of M.

Example 3.2.2    M = <Q, , , , , q₀, Z₀, F> is a pushdown transducer if Q = {q₀, q₁, q₂}; = {a, b}; = {a, b}; = {Z₀, c}; = {(q₀, a, , q₀, c, ), (q₀, b, , q₀, c, ), (q₀, , , q₁, , ), (q₁, a, c, q₁, , a), (q₁, b, c, q₁, , b), (q₁, , Z₀, q₂, Z₀, )}; and F = {q₂}.

By definition, in each transition rule (q, , , p, , ) the entries q and p are states in Q, is either an input symbol or an empty string, is either a pushdown symbol or an empty string, is a string of pushdown symbols, and is either an output symbol or an empty string.

Each pushdown transducer M = <Q, , , , , q₀, Z₀, F> can be graphically represented by a transition diagram of the following form. For each state in Q the transition diagram has a corresponding node drawn as a circle. The initial state is identified by an arrow from nowhere that points to the corresponding node. Each accepting state is identified by a double circle. Each transition rule (q, , , p, , ) is represented by an edge from the node that corresponds to state q to the node that corresponds to state p. In addition, the edge is labeled with

For notational convenience, edges that agree in their origin and destination are merged, and their labels are separated by commas.

Example 3.2.3    Figure 3.2.3 gives the transition diagram for the pushdown transducer of Example 3.2.2.

Figure 3.2.3 A transition diagram of a pushdown transducer.

on the edge that starts and ends at state q₀ corresponds to the transition rule (q₀, a, , q₀, , ). The label

on the edge that starts at state q₀ and ends at state q₁ corresponds to the transition rule (q₀, , , q₁, , ).

The top row "/" in the label

corresponds to the input tape. The middle row "/" corresponds to the pushdown tape. The bottom row "/" corresponds to the output tape.

Throughout the text the following conventions are assumed for each production rule (q, , , p, , ) of a pushdown transducer. The conventions do not affect the power of the pushdown transducers, and they are introduced to simplify the investigation of the pushdown transducers.

1.  If = Z₀, then Z₀ is a prefix of .
2.   is a string of length 2 at most.
3.  If is a string of length 2, the is equal to the first symbol in .

 Configurations and Moves of Pushdown Transducers

On each input x from * the pushdown transducer M has some set of possible configurations (see Figure 3.2.4). Each configuration , or instantaneous description, of M is a triplet (uqv, z, w), where q is a state of M, uv = x is the input of M, z is a string from * of pushdown symbols, and w is a string from * of output symbols. Intuitively, a configuration (uqv, z, w) says that M on input x can reach state q with z in its pushdown store, after reading u and writing w. With no loss of generality it is assumed that and Q are mutually disjoint.

Figure 3.2.4 A configuration of a pushdown transducer.

The configuration is said to be an initial configuration if q = q₀, u = w = , and z = Z₀. Such an initial configuration says that M is in its initial state q₀, with none of the input symbols being read yet (i.e., u = ), with the output being still empty (i.e., w = ), and the pushdown being still in its original stage (i.e., z = Z₀). In addition, the configuration says that M is given the input v.

The configuration is said to be an accepting configuration if v = and q is an accepting state. Such an accepting configuration says that M reached an accepting state after reading all the input (i.e., v = ) and writing w. In addition, the configuration says that the input M has consumed is equal to v.

Example 3.2.4    Consider the pushdown transducer M whose transition diagram is given in Figure 3.2.3. (q₀abbb, Z₀, ) is the initial configuration of M on input abbb. The configuration (abq₁bb, Z₀cc, ) of M says that M consumed already u = ab from the input, the remainder of the input is v = bb, M has reached state q₁ with the string Z₀cc in the pushdown store, and the output so far is empty. The configurations are illustrated in Figure 3.2.5(a) and Figure 3.2.5(b), respectively.

Figure 3.2.5 Configurations of the pushdown transducer of Figure 3.2.3.

(abbbq₂, Z₀, bb) and (abq₂bb, Z₀cc, ) are also configurations of M₀. The first configuration is accepting. The second, however, is not an accepting configuration despite its being in an accepting state, because the input has not been consumed until its end.

The transition rules of M are used for defining the possible moves of M. Each move is in accordance with some transition rule. A move on transition rule (q, , , p, , ) changes the state of the finite-state control from q to p; reads from the input tape, moving the input head || positions to the right; writes in the output tape, moving the output head || positions to the right; and replaces on top of the pushdown store (i.e., from the location of the pushdown head to its left) the string with the string , moving the pushdown head || - || positions to the right. The move is said to be a pop move if || < ||. The move is said to be a push move if || < ||. The symbol under the pushdown head is called the top symbol of the pushdown store.

A move of M from configuration C₁ to configuration C₂ is denoted C_{1 M} C₂, or simply C₁ C₂ if M is understood. A sequence of zero or more moves of M from configuration C₁ to configuration C₂ is denoted C_{1 M} * C₂, or simply C₁ * C₂, if M is understood.

Example 3.2.5    The pushdown transducer whose transition diagram is given in Figure 3.2.3, has a sequence of moves on input abbb that is given by the following sequence of configurations: (q₀abbb, Z₀, ) (aq₀bbb, Z₀c, ) (abq₀bb, Z₀cc, ) (abq₁bb, Z₀cc, ) (abbq₁b, Z₀c, b) (abbbq₁, Z₀, bb) (abbbq₂, Z₀, bb). This sequence is the only one that can start at the initial configuration and end at an accepting configuration for the input abbb. The sequence of configurations is depicted graphically in Figure 3.2.6.

Figure 3.2.6 Transition between configurations of the pushdown transducer of Figure 3.2.3.

All the moves of M on the transition rules that both start and end at state q₀ are push moves. All the moves of M on the transition rules that both start and end at state q₁ are pop moves.

A string in the pushdown store that starts at the bottom symbol and ends at the top symbol, excluding the bottom symbol, is called the content of the pushdown store. The pushdown store is said to be empty if its content is empty.

Example 3.2.6    Let M be the pushdown transducer of Figure 3.2.3. Consider the computation of M on input abbb (see Figure 3.2.6). M starts with an empty pushdown store, adding c to the store during the first move. After the second move, the content of the pushdown store is cc. The content of the pushdown store does not change during the third move.

 Determinism and Nondeterminism in Pushdown Transducers

The definitions of determinism and nondeterminism in pushdown transducers are, in principal, similar to those provided for finite-state transducers. The difference arises only in the details.

A pushdown transducer M = <Q, , , , , q₀, Z₀, F> is said to be deterministic if for each state q in Q; each input symbol a in ; and each pushdown symbol Z in , the union (q, a, Z) (q, a, ) (q, , Z) (q, , ), is a multiset that contains at most one element.

Intuitively, M is deterministic if the state and the top pushdown symbol are sufficient for determining whether or not a symbol is to be read from the input, and the state, the top pushdown symbol, and the input to be read are sufficient for determining which transition rule is to be used.

A pushdown transducer is said to be nondeterministic if it is not a deterministic pushdown transducer.

Example 3.2.7    Let M₁ be the pushdown transducer whose transition diagram is given in Figure 3.2.3.

In a move from state q₁, the pushdown transducer M₁ reads an input symbol if and only if the topmost pushdown symbol is not Z₀. If the symbol is not Z₀, then the next symbol in the input uniquely determines which transition rule is to be used in the move. If the topmost pushdown symbol is Z₀, then M₁ must use the transition rule that leads to q₂. Consequently, the moves that originate at state q₁ can be fully determined "locally."

On the other hand, the moves from state q₀ cannot be determined locally, because the topmost pushdown symbol is not sufficient for determining if an input symbol is to be read in the move.

It follows that M₁ is a nondeterministic pushdown transducer. However, the pushdown transducer M₂ whose transition diagram is given in Figure 3.2.7 is deterministic.

Figure 3.2.7 A deterministic pushdown transducer.

To move from state q₀ the pushdown transducer M₂ has to read an input symbol. If it reads the symbol a, then the move takes M₂ to state q_a. If it reads the symbol b, then the move takes M₂ to state q_b.

The topmost symbol in the pushdown store determines whether M₂ must enter state q₀ or state q_a on a move that originates at state q_a. If the topmost symbol is Z₀, then M moves to state q₀. If the topmost symbol is a, then M moves to state q_a. In the latter case M uses the transition rule (q_a, a, a, q_a, aa, c) if the input symbol to be read is a, and it uses the transition rule (q_a, b, a, q_a, , ) if the symbol to be read is b.

 Computations of Pushdown Transducers

The computations of the pushdown transducers are also defined like the computations of the finite-state transducers. An accepting computation of a pushdown transducer M is a sequence of moves of M that starts at an initial configuration and ends at an accepting one. A nonaccepting , or rejecting, computation of M is a sequence of moves on an input x, for which the following conditions hold.

1.  The sequence starts from the initial configuration of M on input x.
2.  If the sequence is finite, it ends at a configuration from which no move is possible.
3.  M has no accepting computation on input x.

A computation is said to be a halting computation if it consists of a finite number of moves.

Example 3.2.8    Consider the pushdown transducer M whose transition diagram is given in Figure 3.2.7. The pushdown transducer has accepting computations only on those inputs that have the same number of a's as b's. On each input w in which the pushdown transducer has an accepting computation, it writes the string cⁱ onto the output tape, where i = (the number of a's in w) = (the number of b's in w).

The pushdown transducer enters state q₀ whenever the portion of the input read so far contains the same number of a's and b's. The pushdown transducer enters state q_a whenever the portion of the input read so far contains more a's than b's. Similarly, the pushdown transducer enters state q_b whenever the portion of the input read so far contains more b's than a's. The pushdown store is used for recording the difference between the number of a's and the number of b's, at any given instant of a computation.

On input aabbba the pushdown transducer M has only one computation. M starts the computation by moving from state q₀ to state q_a, while reading a, writing c, and pushing a into the pushdown store. In the second move M reads a, writes c, pushes a into the pushdown store, and goes back to q_a. In the third and fourth moves M reads b, pops a from the pushdown store, and goes back to state q_a. In the fifth move M goes to state q₀ without reading, writing, or changing the content of the pushdown store. In the sixth move M reads b, pushes b into the pushdown store, and moves to state q_b. In its seventh move M reads a, pops b from the pushdown store, writes c, and goes back to q_b. The computation terminates in an accepting configuration by a move from state q_b to state q₀ in which no input is read, no output is written, and no change is made in the content of the pushdown store.

By definition, each move in each computation must be on a transition rule that keeps the computation in a path, that eventually causes the computation to read all the input and halt in an accepting state. Whenever more than one such alternative in the set of feasible transition rules exists, then any of these alternatives can be chosen. Similarly, whenever none of the feasible transition rules satisfies the conditions above, then any of these transition rules can be chosen. This observation suggests that we view the computations of the pushdown transducers as also being executed by imaginary agents with magical power.

An input x is said to be accepted , or recognized, by a pushdown transducer M if M has an accepting computation on x. An accepting computation on x that terminates in a configuration of the form (xq_f, z, w) is said to have an output w. The output of a nonaccepting computation is assumed to be undefined.

Example 3.2.9    Consider the pushdown transducer M, whose transition diagram is given in Figure 3.2.3. The pushdown transducer accepts exactly those inputs that have even length. In each accepting computation the pushdown transducer outputs the second half of the input.

As long as the pushdown transducer is in state q₀, it repeatedly reads an input symbol and stores c in the pushdown store. Alternatively, as long as the pushdown transducer is in state q₁, it repeatedly reads an input symbol and pops c from the pushdown store.

Upon reaching an empty pushdown store, the pushdown transducer makes a transition from state q₁ to state q₂ to verify that the end of the input has been reached. Consequently, in its accepting computations, the pushdown transducer must make a transition from state q₀ to state q₁ upon reaching the middle of its inputs.

On input abbb the pushdown transducer starts (its computation) with two moves, reading the first two input symbols, pushing two c's into the pushdown store, and returning to state q₀. In its third move the pushdown transducer makes a transition from state q₀ to state q₁.

The pushdown transducer continues with two moves, reading the last two symbols in the input, popping two c's from the pushdown store, and copying the input being read onto the output tape.

The pushdown concludes its computation on input abbb by moving from state q₁ to state q₂.

If M on input abbb reads more than two input symbols in the moves that originate at state q₀, it halts in state q₁ because of an excess of symbols in the pushdown store. If M on input abbb reads fewer than two input symbols in the moves that originates at state q₁, it halts in state q₁ because of a lack of symbols in the pushdown store. In either case the sequences of moves do not define computations of M.

This example shows that, on inputs accepted by a pushdown transducer, the transducer may also have executable sequences of transition rules which are not considered to be computations.

Other definitions, such as those of the relations computable by pushdown transducers, the languages accepted by pushdown transducers, and the languages decided by pushdown transducers, are similar to those given for finite-state transducers in Section 2.2.

Example 3.2.10    The pushdown transducer M₁, whose transition diagram is given in Figure 3.2.3, computes the relation { (xy, y) | xy is in {a, b}*, and |x| = |y| }.

The pushdown transducer M₂, whose transition diagram is given in Figure 3.2.7 computes the relation { (x, cⁱ) | x is in {a, b}*, and i = (number of a's in x) = (number of b's in x) }.

 From Recursive Finite-Domain Programs to Pushdown
Transducers

The simulation of recursive finite-domain programs by pushdown transducers is similar to the simulation of the finite-memory programs by the finite-state transducers, as long as no call and return instructions are encountered. In such a case the pushdown transducers just trace across the states of the programs without using the pushdown store.

Upon reaching the call instructions, the pushdown transducers use their store to record the states from which the calls originate. Upon reaching the return instructions, the pushdown transducers retrieve from the store the states that activated the corresponding calls, and use this information to simulate the return instructions.

Specifically, consider any recursive finite-domain program P. Assume that P has m variables x₁, . . . , x_m, and k instruction segments I₁, . . . , I_k. Denote the initial value with in the domain of the variables of P. Let a state of P be an (m + 1)-tuple [i, v₁, . . . , v_m], where i is a positive integer no greater than k and v₁, . . . , v_m are values from the domain of the variables of P.

The computational behavior of P can be modeled by a pushdown transducer M = <Q, , , , , q₀, Z₀, F> whose states are used for recording the states of P, whose transition rules are used for simulating the transitions between the states of P, and whose pushdown store is used for recording the states of P which activated those executions of the procedures that have not been deactivated yet. Q, , , , , q₀, Z₀, and F are defined in the following manner.

Q

is a set containing of all those states that P can reach.

is a set consisting of all those input values that P can read.

is a set containing Z₀ and all the call states in Q. Z₀ is assumed to be a new element not in Q, and a call state is assumed to be a state that corresponds to a call instruction.

is a set containing all the output values that P can write.

q₀

denotes the state [1, , . . . , ] of P.

F

denotes the set of all those states in Q corresponding to an instruction of the form if eof then accept.

contains a transition rule of the form (q, , , p, , ) if and only if q = [i, u₁, . . . , u_m] and p = [j, v₁, . . . , v_m] are states in Q that satisfy the following conditions.

1.  By executing the instruction segment I_i, the program P (with values u₁, . . . , u_m in its variables x₁, . . . , x_m, respectively) can read , write , and reach instruction segment I_j with respective values v₁, . . . , v_m in its variables.
2.  If I_i is neither a call instruction nor a return instruction, then = = . That is, the pushdown store is ignored.
3.  If I_i is a call instruction, then = and = q. That is, the state q of P prior to invoking the procedure is pushed on top of the store. The state is recorded to allow the simulation of a return instruction that deactivates the procedure's activation caused by I_i.
4.  If I_i is a return, instruction then is assumed to be a state of P, and the transition from state q to state p is assumed to deactivate a call made at state . In such a case = .

Example 3.2.11    Consider the recursive finite-domain program P in Figure 3.1.1 with {0, 1} as the domain of its variables. The program is abstracted by the pushdown transducer whose transition diagram is given in Figure 3.2.8.

Figure 3.2.8 The transition diagram of a pushdown transducer that characterizes the recursive finite-domain program of Figure 3.1.1.

On moving from state [3, 0, 0, 0] to state [4, 0, 0, 0], the pushdown transducer reads the value 0 into x. On moving from state [3, 0, 0, 0] to state [4, 1, 0, 0], the pushdown transducer reads the value 1 into x.

Each move from state [5, 1, 0, 0] to state [7, 1, 1, 0] corresponds to a call instruction, and each such move stores the state [5, 1, 0, 0] in the pushdown store. In each such move, the value of y in state [7, 1, 1, 0] is determined by the value of x in state [5, 1, 0, 0], and the values of x and z in [7, 1, 1, 0] are determined by the values of x and z in state [5, 1, 0, 0].

Each move from state [10, 1, 1, 0] to state [6, 1, 0, 0] that uses the transition rule ([10, 1, 1, 0], , [5, 1, 0, 0], [6, 1, 0, 0], , , ) corresponds to an execution of a return instruction for a call that has been originated in state [5, 1, 0, 0]. The value of x in state [6, 1, 0, 0] is determined by the value of y in state [10, 1, 1, 0]. The values of y and z state [6, 1, 0, 0] are determined by values of y and z in state [5, 1, 0, 0].

The pushdown transducer has the following computation on input 0011.

 From Pushdown Transducers to Recursive Finite-Domain
Programs

Using the previous discussion, we conclude that there is an algorithm that translates any given recursive finite-domain program into an equivalent pushdown transducer. Conversely, there is also an algorithm that derives an equivalent recursive finite-domain program from any given pushdown transducer M = <Q, , , , , q₀, Z₀, F>. The recursive finite-domain program can be a table-driven program of the form shown in Figure 3.2.9. The program simulates the pushdown transducer in a manner similar to that of simulating a finite-state transducer by a finite-memory program as shown in Section 2.2. The main difference is in simulating the effect of the pushdown store.

state := q0
do
    top := Z0
    call RP(top)                        /* Record the bottom pushdown symbol Z0. */
until false
procedure RP(top)
    do
        /* Accept if an accepting state of M is reached at the end of the input.   
     */
        if F(state) then
            if eof then accept
        /* Nondeterministically find the entries of the transition rule (q, , , p, , )
        that M uses in the next simulated move.                                                 */
        do in := e or read in until true                      /*              in :=  */
        do pop := e or pop := top until true                /*           pop :=  */
        next_ state := ?                                          /* next_ state := p */
        push := ?                                                 /*         push :=  */
        out := ?                                                   /*            out :=  */
        if not (state,in,pop,next_ state,push,out) then reject
        /* Simulate the next move of M. */
        state := next_ state
        if out e then write out
        if pop e then return
        if push e then call RP(push)
    until false
end                                                                                                                    

The program uses the variable state for recording the states that M leaves in its moves, the variable top for recording the topmost symbol in the pushdown store, the variable in for recording inputs that M consumes in its moves, the variable next_ state for recording the states that M enters in its moves, the variable pop for recording the substrings that are replaced on top of the pushdown store, the variable push for recording the changes that have to be made on top of the pushdown store, and a variable out for recording the outputs that have to be written in the moves of M.

The content of the pushdown store is recorded indirectly through recursion. Each pushing of a symbol is simulated by a recursive call, and each popping of a symbol is simulated by a return.

The main program initializes the variable state to q₀, and calls RP to record a pushdown store containing only Z₀.

The body of the recursive procedure RP consists of an infinite loop. Each iteration of the loop starts by checking whether an accepting state of M has been reached at the end of the input. If such is the case, the program halts in an accepting configuration. Otherwise, the program simulates a single move of M. The predicate F is used to determine whether state holds an accepting state.

The simulation of each move of M is done in a nondeterministic manner. The program guesses the input to be read, the top portion of the pushdown store to be replaced, the state to be reached, the replacement to the top of the store, and the output to be written. Then the program uses the predicate for determining the appropriateness of the guessed values. The program aborts the simulation if it determines that the guesses are inappropriate. Otherwise, the program records the changes that have to be done as a result of the guessed transition rule.

The variables of the program are assumed to have the domain Q {e}, with e being a new symbol. In addition, with no loss of generality, it is assumed that each transition rule (q, , , p, , ) of M satisfies either || + || = 1 or = = Z₀. The latter assumptions are made to avoid the situation in which both a removal and an addition of a symbol in the pushdown store are to be simulated for the same move of M.

Example 3.2.12    For the pushdown transducer of Figure 3.2.3 the table-driven program has the domain of variables equal to {a, b, Z₀, c, q₀, q₁, q₂, e}. The truth values of the predicates F and are defined by the corresponding tables in Figure 3.2.10.

Figure 3.2.10 Tables for a table-driven recursive finite-domain program that simulates the pushdown transducer of Figure 3.2.3.

The pushdown transducer can be simulated also by the non-table-driven program of Figure 3.2.11.

state := q0
next_ top := Z0
call RP(next_ top)
procedure RP(top)
    do
        if state = q0 then
            do
                read in
                if (in a) and (in b) then reject
                next_ top := c
            call RP(next_ top)
            or
                state := q1
           until true
      if state = q1 then
            do
                if top = Z0 then state := q2
               if top = c then
                    do
                        read in
                        if (in a) and (in b) then reject
                        write in
                        return
                    until true
        until false
      if state = q2 then
            if eof then accept
    until false
end                                                                          

In a manner similar to the one discussed in Section 2.2 for finite-state transducers, the recursive finite-domain program can be modified to be deterministic whenever the given pushdown transducer is deterministic.

A formalization of the previous discussion implies the following theorem.

Theorem 3.2.1    A relation is computable by a nondeterministic (respectively, deterministic) recursive finite-domain program if and only if it is computable by a nondeterministic (respectively, deterministic) pushdown transducer.

 Pushdown Automata

Pushdown transducers whose output components are ignored are called pushdown automata. Formally, a pushdown automaton is a tuple <Q, , , , q₀, Z₀, F>, where Q, , , q₀, Z₀, and F are defined as for pushdown transducers, and is a relation from Q × ( {}) × ( {})   to   Q × *.

As in the case for pushdown transducers, the following conditions are assumed for each transition rule (q, , , p, ) of a pushdown automaton.

1.  If = Z₀, then Z₀ is a prefix of .
2.   is a string of length 2 at most.
3.  If is a string of length 2, then is equal to the first symbol in .

Example 3.2.13    The pushdown automaton M that is induced by the pushdown transducer of Figure 3.2.3 is <Q, , , q₀, F>, where Q = {q₀, q₁, q₂}, = {a, b}, = {Z₀, c}, = {(q₀, a, , q₀, c), (q₀, b, , q₀, c), (q₀, , , q₁, ), (q₁, a, c, q₁, ), (q₁, b, c, q₁, ), (q₁, , Z₀, q₂, Z₀)}, and F = {q₂}. The pushdown automaton is represented by the transition diagram of Figure 3.2.12.

Figure 3.2.12 A transition diagram of a pushdown automaton.

The pushdown automaton is said to be deterministic if for each state q in Q, each input symbol a in , and each pushdown symbol Z in the union (q, a, Z) (q, a, ) (q, , Z) (q, , ) is a multiset that contains at most one element. The pushdown automaton is said to be nondeterministic if it is not a deterministic pushdown automaton.

A configuration , or an instantaneous description, of the pushdown automaton is a pair (uqv, z), where q is a state in Q, uv is a string in *, and z is a string in *. Other definitions, such as those for initial and final configurations, _M , , _M *, *; and acceptance, recognition, and decidability of a language by a pushdown automaton, are similar to those given for pushdown transducers.

Example 3.2.14    The transition diagram in Figure 3.2.13

Figure 3.2.13 Transition diagram of a deterministic pushdown automaton that accepts { aibi | i 0 }.

The transition diagram in Figure 3.2.14

Figure 3.2.14 Transition diagram of a nondeterministic pushdown automaton that accepts { wwrev | w is in {a, b}* }.

[next] [prev] [prev-tail] [front] [up]