Chapter 6

Pushdown Automata

Thp context-free languages have a type of antoniatou that defines theiu. This automaton, called a pushdown automaton, is an extension of the nondeterministic finite automaton with e-transitions, which is one of the ways to define the regular languages. The pushdown automaton is essentially an e-NFA with the addition of a stack. The stack can be read, pushed, and popped only at the top, just like the stack data structure.

In this chapter, we define two different versions of tlie pushdown automaton: one that accepts by entering an accepting state, like finite automata do, and another version that iy:copts by emptying its stack, regardless of the state it is in. We show that these two variations accept exactly the context-free languages; that is, grammars can be converted to equivalent pushdown automata, and vice-versa. We also consider briefiy the subclass of pushdown automata that is deterministic. These accept all the regular languages, but only a proper subset of the CFLs. Since they resemble closely the mechanics of the parser in a typical compiler, it is important to observe what language constructs can and cannot be recognized by deterministic pushdown automata.

6.1 Definition of the Pushdown Automaton

In this section we hitroduce the pushdown automaton, first informally, then as a formal construct.

6.1.1 Informal Introduction

The pushdown automaton is in essence a nondetermuiistic finite automaton with e-transitions permitted and one additional capability: a stack on wldch it can store a string of stack symbols. The presence of a stack means that, unlike the finite automaton, the pushdown automaton can remember an infinite amount of information. However, unlike a general-purpose computer, which also has the ability to remember arbitrarily large amounts of information, the

pushdown automaton can (mly access tho information on its stack in a last-in-first-out way.

As a result, there arc languages that could be recognized by some computer program, but are not recognizable by any pushdown automaton. In fact, pushdown automata rec:ognize all and onlj- the context-free languages. While tliere are main languages that ате context-free, including some we have seen that are not regular languages, there are also some simphvto-describe languages that are not context-free, as we shall see in Section 7,2. An example of a non-context-fi-ee language is {0 Г 2 n > 1), the set of strings consisting of equal groups of Os, Is, and 2s.

Input

Finite

state

control

Accept/reject

Stack

Figure 6.1: A pushdown automaton is essentially a finite automaton with a stack data structure

We can view the pushdown automaton informally as the device suggested in Fig. 6.1, A finite-state control reads inputs, one symbol at a time. The pushdown automaton is allowed to observe the symbol at the top of the stack and to base its transition on its current state, the input symbol, and the symbol at the top of stack. Alternatively, it may make a spontaneous transition, using f as its input instead of an input sjmibol. In one transition, the pushdown automaton:

1, Consumes from the input the symbol that it uses in the transition. If e is used for the input, then no input symbol is consumed.

2, Goes to a new- state, which may or may not be the same as the previous state.

3, Replaces the symbol at the top of the stack by any string. The string could be f; which corr<?sponds to a pop of the stack. It could be the same symbol that a];peared at the top of the stack previously; i.e., no change to the stack is made. It could also replace the top stack symbol by one other symbol, which in effect changes the top of the stack but does not push or pop it. Finally, the top stack symbol could be replaced by two or more symbols, which has the effect of (possibly) changing the top stack symbol, and then pushing one or more new symbols onto the stack.

1. Start in a state that represents a guess that we have not yet seen the middle; i.e., we have not seen the end of the string w that is to be followed by its own reverse. While in state qo, we read symbols and store them on the stack, by pushing a copy of each input symbol onto the stack, in turn.

2. At any time, we may guess that we have seen the middle, i.e., the end of w. At this time, w will be on the stack, with the right end of w at the top and the left end at the bottom. We signify this choice by spontaneously going to state qi. Since the automaton is nondeterministic, we actually make both guesses: we guess we have seen the end of u;, but we also stay in state qo and continue to read inputs and store them on the stack.

3. Once in state q\, we compare input symbols with the symbol at the top of the stack. If they match, we consume the input symbol, pop the stack, and proceed. If they do not match, we have guessed wrong; our guessed w was not followed by ш. This branch dies, although other branches of the nondeterministic automaton may survive and eventually lead to acceptance.

4. If we empty the stack, then we have indeed seen some input w followed by u). We accept the input that was read up to this point.

□

6.1.2 The Formal Definition of Pushdown Automata

Our formal notation for a pushdown automaton (PDA) involves seven components. We \vrite the specification of a PD.4 P as follows:

P = iQ,E,r,S,qo,Zo,F)

The components have the following meanings;

Q: A finite set of states, like the states of a finite automaton.

VVe could also design a pushdown automaton for Lj,;, whicli is the language whose grammar appeared in Fig. H.l. However, Лшт is slightly simpler and will allow us to focus on the important ideas regarding pu.shdown automata.

Example 6.1: Let us consider the language

Lu-ur = {ww I w is in (0 + 1)*}

This language, often referred to as u;-w-reversed, is the even-length palindromes over alphabet {0,1}. It is a CFL, generated by the grammar of Fig. 5.1, with the productions P 0 and f 1 omitted.

We can design an informal pushdown automaton accepting !/, ., as follows.