Introduction To Push-down Automata

Push-down Automata: A push-down automaton (PDA) is a structure (Q,Σ, Γ, δ, q0, z0, F) where Q is a finite set of states, Σ is the input alphabet, Γ is the stack alphabet (that usually includes the input alphabet Σ), q0 is the initial state, F ⊆ Q is the set of accepting states, z0 the initial stack symbol, and
δ : Q × (Σ ∪ {ε}) × Γ → 2Q×Γ∗.
In each move, a PDA can optionally read an input symbol. However, in each move, it must read the top of the stack (later, we will see that this assumption comes in handy when we have to convert a PDA to a CFG). Since we will always talk about an NPDA by default, the δ function returns a set of nondeterministic options. Each option is a next-state to go to, and a stack string to push on the stack, with the first symbol of the string appearing on top of the stack after the push is over. For example, if q1, ba ∈ δ(q0, x, a), the move can occur when x can be read from the input and the stack top is a. In this case, the PDA moves over x (it cannot read x again). Also, an a is removed from the stack. However, as a result of the move, an a is promptly pushed back on the stack, and is followed by a push of b, with the machine going to state q1. The transition function δ of a PDA may be either deterministic or nondeterministic.

DPDA versus NPDA: A push-down automaton can be deterministic or nondeterministic. DPDA and NPDA are not equivalent in power; the latter are strictly more powerful than the former. Also, notice that unlike with a DFA, a deterministic PDA can move on ε. Therefore, the exact specification of what deterministic means becomes complicated. We summarize the definition from [60]. A PDA is deterministic if and only if the following conditions are met:

1. δ(q, a,X) has at most one member for any q in Q, a in Σε, and X in Γ.
   
2. If δ(q, a,X) is non-empty, for some a in Σ, then δ(q, ε,X) must be empty.
   

In this book, I will refrain from giving a technically precise definition of DPDAs. It really becomes far more involved than we wish to emphasize in this chapter, at least. For instance, with a DPDA, it becomes necessary to know when the string ends, thus requiring a right end-marker .

Deterministic context-free languages (DCFL)

A deterministic context-free language (DCFL) is one for which there is a DPDA that accepts the same language. Consider the language
Language L0 = {wwR | w ∈ {0, 1}∗}.

L0 is not a DCFL because in any PDA, the use of nondeterminism is essential to “guess” the midpoint. Figure 13.6 presents the δ function of a PDA designed to recognize L0. This PDA is described by the structure

PL0 = ({q0, }, {0, 1}, {0, 1, z0}, δ, q0, z0, {q0, q2}).

This PDA begins by stacking 0 or 1, depending on what comes first. The comments 1a and 1b describe the nondeterministic selection of assuming not being at a midpoint, and being a midpoint, respectively. A similar logic is followed in 2a and 2b as well. Chapter 14 describes PDA construction in greater detail. Let us further our intuitions about PDAs by considering a few languages:

L1: {aibjck | if i = 1 then j = k}.
L2: {aibjckdm | i, j, k,m ≥ 0 ∧ if i = 1 then j = k else k = m}
L3: {ww | w ∈ {0, 1}∗}.
L4: {0, 1}∗ \ {ww | w ∈ {0, 1}∗}.
L5: {aibjck | i = j or i = k}.
L6: {anbncn | n ≥ 0}.

L1 is a DCFL, because after seeing whether i = 1 or not, a deterministic algorithm can be employed to process the rest of the input. A DPDA can be designed for reverse(L1) also. Likewise, a DPDA can be designed for L2. However, as discussed in Section 8.1.4, reverse(L2) is not a DCFL, as it is impossible to keep both decisions – whether j = k or k = m – ready by the time i is encountered. L3 is not a CFL at all. However, L4, the complement of L3, is a CFL. L5 is a CFL (but not a DCFL) – the guesses of i = j or i = k can be made nondeterministically. Finally, L6 is not a CFL, as we cannot keep track of the length of three distinct strings using one stack.