Theory of Computation

CHAPTER 4

ADDING A STACK TO A NFA: PUSHDOWN AUTOMATA

FA, and therefore NFA, accept some reasonably nontrivial languages over some alphabet ∑, yet they fail decisively on certain simple languages, such as L = {0ⁿ 1ⁿ : n ≥ 0} over Σ = {0, 1}, as we showed in 3.1.3.2. This language is an abstraction of a special case of “the set of strings of balanced brackets”,¹²⁵ that is, L_B = {(ⁿ)ⁿ: n ≥ 0} over A = {(,)}. Balanced brackets play an important role in the definition of syntax, and subsequently in the syntactic analysis of formulae, and of programming language constructs. In the latter domain, the result of 3.1.3.2, for example, makes it impossible for an automaton to recognize and pass string constants to the language translator of Algol 60. The reason is that such strings have a balanced bracket structure—where the brackets in this context are left and right quotes, “and”. This does not happen with other major programming languages that do not define strings this way.

In this chapter we will add slightly to the power of the NFA, without going all the way back to the full-fledged URM, so that languages such as L and L_B are acceptable.

  4.0.0.4 Remark. Translating the notation of 1.6.0.10 to grammar notation, we see at once that L = L(G), where G is the CFG over Σ = {0, 1} with just two rules:

That is, this language is context free (type-2).

We will see that the augmented NFA of ...